普通的二分查找法

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

1
2
3
4
5
6
7
8
9
10
11
12
def binarySearch(arr, target):
    start = 0
    end = len(arr)-1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] > target:
            end = mid - 1
        elif arr[mid] < target:
            start = mid + 1
        else:
            return mid
    return -1

修改过的二分查找法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def binarySearch(arr, target):
    start = 0
    end = len(arr) - 1
    while start + 1 < end:
        mid = (start + end) // 2
        if arr[mid] > target:
            end = mid
        elif arr[mid] < target:
            start = mid
        else:
            end = mid
    if arr[start] == target:
        return start
    elif arr[end] == target:
        return end
    else:
        return -1

若将条件改为查找target最后一次出现的下标（从0开始），那么程序将发生改变，循环中如果 arr[mid] = target, 则 start = mid; 且最后的边界判断改为先判断arr[end] == target; 其他不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binarySearch(arr, target):
    start = 0
    end = len(arr) - 1
    while start + 1 < end:
        mid = (start + end) // 2
        if arr[mid] > target:
            end = mid
        elif arr[mid] < target:
            start = mid
        else:
            start = mid

    if arr[end] == target:
        return end
    elif arr[start] == target:
        return start
    else:
        return -1

注意：

  • 已排序很重要，而且排序是降序还是升序写法也不一样。
  • 写程序先写异常处理，这里对应的是数组为空的情况。
  • start 和 end 分别初始化为 0 和 array.size() - 1。
  • 取中值使用 mid = start + (end - start) / 2; 目的是为了防止 start + end 的值超出int范围发生溢出错误。
  • 循环停止条件为 start < end-1;没有等号，如果取等号，那么有可能进入死循环，如：start = 1； end = 2； 那么 mid = 1；那么此时如果令 start = mid，程序将进入死循环。
  • 循环停止时肯定有 start + 1 == end；或者数组元素只有一个，也就是说 start 和 end 要么相邻（数组元素个数大于1），要么相交（数组元素个数为1），那么都可以归结为最后的判断语句，根据题目的要求（第一次出现还是最后一次出现）确定判断顺序。

应用

旋转的数组的最小值

假设一个旋转排序的数组其起始位置是未知的（比如[0 1 2 4 5 6 7] 可能变成是[4 5 6 7 0 1 2]）。
你需要找到其中最小的元素。
假设数组中不存在重复的元素。
思路： 由最小值为中心把两边分开，两边都是递增的，而后一部分的最大值也严格小于前一部分的所有值，显然，最后一部分的最大值就是num[n-1]那么我们只需要找到比这个值小的第一个值即可。

1
2
3
4
5
6
7
8
9
10
def findMin(nums):
    start, end = 0, len(nums)-1
    target = nums[-1]
    while start + 1 < end:
        mid = (start + end) // 2
        if nums[mid] > target:
            start = mid
        else:
            end = mid
    return min(nums[start], nums[end])

旋转排序数组中的最小值 II

假设包含重复值

1
2
3
4
5
6
7
8
9
10
11
def findMin(nums):
    start, end = 0, len(nums) - 1
    while start + 1 < end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid
        elif nums[mid] < nums[end]:
            end = mid
        else:
            end = end - 1
    return min(nums[start], nums[end])