二分查找 (lintcode:first-position-of

二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

例如：
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

我的代码，没用二分查找：

def binarySearch(nums, target):
    try:
        index1 = nums.index(target)
        print index1
    except:
        print -1

网上找的代码，我自己做了点改进：

def binarySearch(nums, target):
        # write your code here
    left, right = 0, len(nums)
    while left + 1 < right :
        mid = (left + right) / 2
        if nums[mid] < target :
            left = mid
        else :
            right = mid
    if right >= len(nums): #这句是我加的，如果没有这句，target大于nums里的最大值会报错：list index out of range
        return -1
    elif nums[left] == target :
        return left
    elif nums[right] == target :
        return right
    else:
        return -1

lintcode 原题

20180103