Binary Search

写好二分查找的技巧

总结自极客时间【数据结构与算法之美】专栏，最基础的二分查找写法：

class Solution:
    def binarySearchBase(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid + 1
            else:
                return mid
        return -1

其中需要注意的有以下几点：

循环退出条件，必须采用小于等于符号
```
     low <= high
```
以一个例子说明，当对 [3, 4] 查找 4 元素时，如果下一次不重新进入循环则无法纠正 mid 指向的索引值；这种 case 通常发生在给定值出现在首、尾时。

   3,           4                     3,          4
   ^            ^            =>       ^           ^
   low, mid     high                  mid         high, low

mid 的取值
为防止整型值溢出而不使用先加后除的等式，改进为：
```
     low + (high - low) / 2
```
或再通过位运算来优化性能 (high - low) >> 1
low 和 high 的更新，需要写为
```
     low = mid -1
     high = mid + 1
```
以避免将 mid 直接赋值给 low 时可能产生的死循环，如当 low, mid, high = 3, 3, 4 时。
模拟下该死循环可能产生的情形，当最后一轮查找时 low 和 high 落在了两个相邻的值时，mid 值为一奇一偶数相加的和除以 2，而其值必然为小数，小数就会因向下取整而与 low 值相同。

典型的变形

最简单的二分查找是： 在不存在重复元素的有序数组中，查找值等于给定值的元素。

以下变形的前提是，数据从小到大排列。

查找第一个值等于给定值的元素

不用追求代码的过度完美，易读便于理解没 bug 的其实更好。

class Solution:
    def binarySearchFirstEqual(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                if mid == 0 or nums[mid-1] != target:
                    return mid
                else:
                    # 如果这里不继续二分而是遍历，则时间复杂度会退化到 O(n)
                    high = mid - 1

        return -1

查找最后一个值等于给定值的元素

当 nums[mid] 值等于 target 且并不是最后一个给定值元素时，我们就更新 low = mid + 1 ，因为结果肯定在 [mid+1, high] 之间。

class Solution:
    def binarySearchLastEqual(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                if mid >= (len(nums) - 1) or nums[mid+1] != target:
                    return mid
                else:
                    low = mid + 1

        return -1

查找第一个大于等于给定值的元素

说明第一个大于等于的元素需要通过判断其前一元素是否小于 target 来确定。

class Solution:
    def binarySearchFirstGreatEqual(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] < target:
                low = mid + 1
            else:
                if mid == 0 or nums[mid-1] < target:
                    return mid
                else:
                    high = mid - 1

        return -1

查找最后一个小于等于给定值的元素

完全以此类推：

class Solution:
    def binarySearchLastLittleEqual(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] < target:
                if mid >= len(nums)-1 or nums[mid+1] > target:
                    return mid
                else:
                    low = mid + 1
            else:
                high = mid - 1

        return -1

实战

剑指 offer 53 II | 递增数组中缺失的元素

题目来源：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/

在一个长度为 n-1 的递增排序数组中，所有数字唯一出现一次；在 0, n-1 内的 n 个数字中只有一个数字不在该数组中，请找出该数字。

请参考图解，整个数组因 x 索引值的差异性而被分为了两组：

0 ~ x-1，满足 nums[x] == x
x ~ n-1，不满足 nums[x] == x

index:    0        1           x-1      x      x+1          n-1
          * ------ * ---------- * ----- * ----- * ---------- *
value:    0        1           x-1     x+1     x+2           n

作图提示参考

以 nums[x] \== x 作为二分判断标准找出 x 索引值，需注意，如当数组中的所有元素都满足 nums[x] == x 则可推断出该数组中缺失的值即为 n。

class Solution:
    def missingNumber(self, nums: List[int], _) -> int:
        low, high = 0, len(nums) - 1
        mid = 0
        while low <= high:
            mid = int(low + (high - low >> 1))
            if nums[mid] == mid:
                low = mid + 1
            else:
                high = mid - 1

        if nums[mid] == mid:
            mid = mid+1
        return mid

剑指 offer 11 | 非单调性数组的二分

题目来源：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
题解参考：

        ^
        |
        |  2    2   2
        |                   1
        |  .    .   .
        |  |    |   |   0   .
        |  |    |   |       |
        +---------------.-------->

对一个可能存在重复的、原本是升序排序的数组，将最开始的若干个元素搬到数组末尾后，请返回该数组中的最小值。

这里需要打破之前可能带下来的固有思维：

每一次循环中，并不是只能仅修改 low 或 high，可能需要同时修改；
二分条件的判断，并不仅局限在 mid、nums[nid] 或 target 中；
low、high 边界值的迭代并不仅为 mid 加减 1。

class Solution:
    def minArray3(self, numbers: List[int]) -> int:
        low, high = 0, len(numbers) - 1
        if numbers[low] < numbers[high]:
            # 整个数组为递增，则首元素最小；
            # 注意判断条件不能为非递减，否则会错判 [3, 1, 3] 等
            return numbers[low]

        mid = int(low + (high - low >> 1))
        while low <= high:
            if numbers[low] < numbers[high]:
                return numbers[low]

            mid = int(low + (high - low >> 1))
            if numbers[low] < numbers[mid]:
                # 左半数组非递减，则最小元素出现在右半数组
                low = mid + 1
            elif numbers[low] > numbers[mid]:
                # 在low ~ high 之间包含了最小值，须同时缩减 low、high 范围
                high = mid
                low += 1
            else:
                # numbers[low] == numbers[mid]
                # 若两者相等，则最小元素必定在 [low, high] 间
                # 又因 low、mid 值相等，故可将 low缩小 1 区间后持续查找
                low += 1

        return numbers[mid]