带重复元素的二分搜索

给定排好序的数组和一个数，从数组中找出最早出现该数的下标。

# coding: utf-8
# @author zhenzong
# @date 2018-05-06 18:49


def binary_search(array, target):
    left, right = 0, len(array) - 1

    while left < right:
        mid = (left + right) >> 1
        if array[mid] < target:
            left = mid + 1
        else:
            right = mid

    return right if array[right] == target else -1


print binary_search([1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7], 5)
print binary_search([1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7], 8)
print binary_search([1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7], 7)
print binary_search([1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7], 1)

# 输出
# 8
# -1
# 15
# 0