Binary Search その壱

当乔恩·本特利将二分搜索问题布置给专业编程课的学生时，百分之90的学生在花费数小时后还是无法给出正确的解答，主要因为这些错误程序在面对边界值的时候无法运行，或返回错误结果。1988年开展的一项研究显示，20本教科书里只有5本正确实现了二分搜索。不仅如此，本特利自己1986年出版的《编程珠玑》一书中的二分搜索算法存在整数溢出的问题，二十多年来无人发现。Java语言的库所实现的二分搜索算法中同样的溢出问题存在了九年多才被修复。

复习一下二分查找

给定上升序列[1, 2, 3, 5, 5, 5, 8, 9]
由于是上升序列, 寻找>/>=target的问题, return r
寻找</<=target的问题, return l
IsLeft:
寻找>: nums[m] <= target, return r
寻找>=: nums[m] < target, return r
寻找<: nums[m] < target, return l
寻找<=: nums[m] <= target, return l
IsRight:
寻找>: nums[m] > target, return r
寻找>=: nums[m] >= target, return r
寻找<: nums[m] >= target, return l
寻找<=: nums[m] > target, return l
这不是需要记忆的, 理解了之后就不需要照着模板写了
找到第一个>=5的元素 // 3
找到最后一个<5的元素 // 2
找到第一个>5的元素 // 6
找到最后一个<=5的元素 // 5

通用模板:
l, r = -1, len(nums), 分别指向了左右边界外一格

l, r = -1, len(nums)
while l + 1 < r:
    mid = l + (r - l) // 2
    if (isLeft(mid)): # 满足左侧条件
        l = mid
    else:
        r = mid

或者

l, r = -1, len(nums)
while l + 1 < r:
    mid = l + (r - l) // 2
    if (isRight(mid)): # 满足右侧条件
        r = mid
    else:
        l = mid

l, r = -1, len(nums) 需要特判, 当遇到需要使用nums[l], nums[r]的时候
而l, r = 0, len(nums) - 1 不需要因为这个特判

while l + 1 < r 是所有模板都能通用的

在 Leetcode 33 Search in rotated sorted array 中, 如果全部写进一个while之中, 由于有 nums[l] <= target <= nums[m] 以及 nums[m] <= target <= nums[r], 这时候如果l, r 未更新过, 则会 overflow, 特判起来很麻烦.
一种解决方法, 可以写成两个while, 一个while用于找到最小值, 一个while用于找到target, 然后就是realm = (m + rot)%len(nums), 这样就回到了vanilla binary search

这时如果不用 realm 的写法, 而写进一个 while 内, l,r 就应该设置为0, len(nums) - 1

首先要问为什么模板里面l, r = -1, len(nums)
因为我们解决二分的策略是将有序序列划为两个部分, 左边的部分不具有某种性质(Blue), 右边的部分具有某种性质(Red), 但题目有可能给出特例, 比如 Full Blue 或者 Full Red
我们来看下面的例子:
Leetcode 34 Find First and Last Position of Element in Sorted Array
[2, 2]
这个时候就是 Full Red 的情况, 所有元素都是相同的, 两个相同的元素不可能有不同的性质, 所以我们需要将l, r设置为-1, len(nums)
当l, r = 0, len(nums) - 1 时, l, r = 0, 1 无法进入循环while l + 1 < r, 然后就得不到正确答案, 要特判. 而l, r = -1, len(nums) 时, l, r = -1, 2, 可以进入循环, 得到正确答案, 前者会出错是因为我们使用了不同的 while 进入条件, 原本是 while l <= r, 而我们使用了限制更强的条件 while l + 1 < r, 这使得我们需要在[2, 2]上再次特判

Big Picture 就是二分问题即特判问题

尽管二分查找的基本思想相对简单，但细节可以令人难以招架 ... — 高德纳

l, r = 0, len(nums) - 1, while l <= r, l = mid + 1, r = mid - 1
或者l, r = -1, len(nums) while l + 1 < r, l = mid, r = mid
每个部分都有特殊情况, 二分问题就是特判问题, 我们在做题的时候需要自己在纸上跑一下经典的特例, 比如说[2, 2], [1], [1, 2], [2, 1], []
题目中遇到需要用到nums[l/r]的时候最好选择l, r = 0, len(nums) - 1, 这样就能避免 r == len(nums) 这种特判
这个模板实际上就是把mid处的特判转移到了l, r处, +1/-1是比较抽象的, 而if r == len(nums) 比较直观, 但是一定记得要写

while l + 1 < r 可以保证一定能跳出循环, 但[2, 2]的情况下甚至不能进入循环
他们写mid + 1, mid - 1, 也是为了避免循环的出现, 有了while l + 1 < r就可以直接写l = m/r = m了, 但需要处理[2, 2]的情况, 要么用l, r = -1, len(nums)解决, 要么特判

如果不涉及 nums[r] 的比较, 上面的就是很好的模板, 涉及 nums[r] 的比较, 就应该避免使用l, r = -1, len(nums), 而是使用l, r = 0, len(nums) - 1, 将特判转移到别的地方

有时候根据题目的需要, 特判是可以在进入 while 之前就做的, 比如 len(nums) == 0

为什么要用`l, r = -1, len(nums)`

就是要处理[2, 2]这种Full Red/Full Blue的情况, 如果题目并没有这种情况, 那么就可以直接使用l, r = 0, len(nums) - 1, 就比如说Leetcode 33 Search in Rotated Sorted Array, 输入的就是rotated sorted array, 根本不会出现Full Red/Full Blue的情况, 直接使用l, r = 0, len(nums) - 1, 最后得到相邻的l, r, 然后判断nums[l]和nums[r]就可以了

グーグル