二分查找

简介

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取 一部分继续查找，将查找的复杂度大大减少。

二分查找的题目变化比较多，但是总结起来就是三种变式，我们可以参考 Leetbook-binary-search

模板

经典二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target。如果目标值存在返回下标，否则返回 -1。

经典二分查找适用于

• 非重复的数组的元素查找

• 查找条件不需要与两边的元素进行比较，找的是特定值

代码

# 经典二分查找
def binarySearch(arr, l, r, target):
    while l <= r:
        pivot = int(l + (r - l)/2)
        if arr[pivot] == target: 
            return pivot
        if arr[pivot] < target:
            l = pivot + 1
        else:
            r = pivot - 1
    return -1 
  
# 递归实现
def binarySearch(arr, l, r, target):
    while l <= r:
        pivot = int(l + (r - l) / 2)
        if arr[pivot] == target:
            return pivot
        if arr[pivot] < target:
            return binarySearch(arr, pivot + 1, r, target)
        else:
            return binarySearch(arr, l, pivot + 1, target)

左闭右开

二分查找的高级模式

• 查找的元素不是一个特定的值，而是一种最近似的值。比如 第一个错误的版本，第一个最接近X的值
• 查找条件需要访问元素的直接右邻居

模板

查找元素靠右的五个条件

• left = 0, right = len(nums) // 左闭右开，为了保证最后一个元素能取到，所以为 len(nums)
• left < right // 这里是没有等号的
• mid = (left + right) >> 1 // mid 靠左才能不死循环
• left = mid + 1 //元素靠右，所以移动是右移
• right = mid // 不动，这里一定要和上面的 len(nums) 及 mid 的取值方式对应起来，不然死循环。

# 查找元素靠右
def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)  # right 是右开的
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # Post-processing:
    # End Condition: left == right
    if left != len(nums) and nums[left] == target:
        return left
    return -1

查找元素靠左，返回的时候直接输出 left - 1 即可

注意点：mid 的位置如何确定

下面举一个例子，我们要从如下数组中，找到第一个1，也就是寻找靠右的元素。

我们现在left指向序号$2$，right指向序号$3$

0 0 [0 1] 1 1

当我们找到1的时候，我们不拒绝它，因为1就是我们需要寻找的数字，我们无法确定是不是第一个，所以right = mid ，而当我们找到0的时候，很确定不是我们要找的，所以left = mid + 1。

当 mid = (left + right) // 2 + 1 即中位数靠右的时候，上面的例子就会陷入死循环出不来，所以一定要靠左。即 mid = (left + right) // 2

# 查找第一个 1，元素靠右
def search_first_one(nums):
    left, right = 0, len(nums)  
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == 0:
           left = mid + 1
        else:
           right = mid
    return right
        
# 查找最后一个 0 ，元素靠左
def search_last_zero(nums):
    left, right = 0, len(nums)  
    while left < right:
        mid = (left + right) // 2 + 1
        if nums[mid] == 0:
           left = mid
        else:
            right = mid - 1
    return left