公瑾总结
本总结参考/复制/修改了很多综合帖的内容，全部参考文档会赋予文章底部。
作者：公瑾
转载请注明出处：https://github.com/yuzhoujr/leetcode
Binary Search | 基础
用途：针对Sorted数组查找的算法
时间复杂度: O(log(n))
二分查找法的前置条件要拥有一个已经Sorted好的序列，这样在查找所要查找的元素时, 首先与序列中间的元素进行比较, 如果大于这个元素, 就在当前序列的后半部分继续查找, 如果小于这个元素, 就在当前序列的前半部分继续查找, 直到找到相同的元素, 或者所查找的序列范围为空为止.
伪代码:
left = 0, right = n -1
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t: left = mid + 1;
x[mid] = t: p = mid; break;
x[mid] > t: right = mid -1;
return -1;
Binary Search | 痛点
十个二分九个错：编程珠玑的作者Jon Bentley，布置作业让他的学生们写二分查找，然后他一个个来看。结果呢，他发现90%是错的。
按照上面的伪代码写出了下列的Python代码
def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
接下来说说二分查找的一些痛点。
痛点1: 溢出
mid = (l+r)//2
在对两个Signed 32-bit数字进行相加时，有可能出现溢出，例如下面这种情况：
left = 1, right = Integer.MAX_VALUE
当left 与 right 之和超过了所在类型的表示范围的话, 这个和就会成为一个很随机的值, 那么 middle 就不会得到正确的值.
所以, 更稳妥的做法应该是这样的
mid = l + (r-l)//2`
痛点2: 边界错误
二分查找算法的边界, 一般来说分两种情况, 一种是左闭右开区间, 类似于 [left, right), 一种是左闭右闭区间, 类似于 [left, right].
等等，区间是个什么鬼，左闭右开，左闭右闭又是个什么鬼？
区间的定义： 区间有开区间和闭区间，其中又分为全开区间（ ），全闭区间[ ]，左开右闭区间( ] 和左闭右开区间 [ ),开区间的意思是区间两处的端点值取不到，而闭区间的端点值就可以取到。
例如区间[2,6),他是一个左闭右开的区间，那么在这2~6之间的数字我都可以取到，而且可以取到2，但不可以取到6.
需要注意的是, 循环体外的初始化条件, 与循环体内的迭代步骤, 都必须遵守一致的区间规则, 也就是说, 如果循环体初始化时, 是以左闭右开区间为边界的, 那么循环体内部的迭代也应该如此. 如果两者不一致, 会造成程序的错误. 比如下面就是错误的二分查找算法:
def binarySearch(arr, target):
l , r = 0, len(arr)
while l < r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
这个算法的错误在于, 在循环初始化的时候, 初始化 r=len(arr), 也就是采用的是左闭右开区间, 而当满足 target < arr[mid] 的条件是, target 如果存在的话应该在 [left, mid) 区间中, 但是这里却把 r 赋值为 mid - 1 了, 这样, 如果恰巧 mid-1 就是查找的元素, 那么就会找不到这个元素.
下面给出两个算法, 分别是正确的左闭右闭和左闭右开区间算法, 可以与上面的进行比较:
左闭右闭：包括End区间，end inclusive
def binarySearch(arr, target):
'''
定义：在[l...r]的范围里寻找target, 因为这里定义是需要将r归入范围区间, inclusive，所以while循环的边界需要包含r
'''
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1 # 明确区间的要求，只要使用过的，一律绕过。
else:
r = mid - 1 # 明确区间的要求，只要使用过的，一律绕过。
return -1
左闭右开，不包括End区间, end exclusive
def binarySearch(arr, target):
'''
定义：在[l...r)的范围里寻找target, 因为这里定义是不需要将end归入范围区间
exclusive，所以while循环的边界小于End即可，因为length本身长度会比index大1
相对应的，每次target的value小于arr[mid]的时候，我们在重新定义新的end时候，
也选择exclusive的模式，r = mid即可
'''
l , r = 0, len(arr)
while l < r:
mid = l + (r-l)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid
return -1
痛点2.5 : 死循环
上面的情况还只是把边界的其中一个写错, 也就是右边的边界值写错, 如果两者同时都写错的话, 可能会造成死循环, 比如下面的这个程序:
l , r = 0, len(arr) - 1
while l <= r:
mid = l + (r-l)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid
else:
r = mid
return -1
这个程序采用的是左闭右闭的区间. 但是,
当 target < arr[mid] 的时候, 那么下一次查找的区间应该为 [mid + 1, right], 而这里变成了 [mid, right];
当 target > arr[mid] 的时候, 那么下一次查找的区间应该为 [left, mid - 1], 而这里变成了 [left, mid]. 两个边界的选择都出现了问题, 因此, 有可能出现某次查找时始终在这两个范围中轮换, 造成了程序的死循环.
Binary Search | 模板选择
@gengwuli 提出了模板一致性的观点，我也十分赞同。公瑾的策略是95%的情况下都用以下模板：
def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
极个别情况会采用以下的模板：
def binary_search(array, target):
start, end = 0, len(array) - 1
while start + 1 < end:
mid = (start + end) / 2
if array[mid] == target:
start = mid
elif array[mid] < target:
start = mid
else:
end = mid
if array[start] == target:
return start
if array[end] == target:
return end
return -1
至于为什么不采用一个模板，是因为在大部分题的时候，运用第一种模板能够有更好的可读性
而第二个模板专门针对的是第一个模板的短板：当要access数组边界的数，如果边界的数在运行中出现更改，可能越界。虽然这种情况也可以用Edge Case来写，但太过麻烦。这点我们后面具体说来。
这里插一句话：用的惯的模板才是最适合你的，切记
Binary Search | 题型
题目类型分为三类:
- 有明确Target
- 没有明确Target
- 没有明确Target (可越界类型）
第一类题：有明确Target的题型
这一类题，会要求你找一个Target值，一般找到就返回Target值的下标或者Boolean函数。基础题目举两个例子：
Leetcode 374. Guess Number Higher or Lower
告知Target是1到N之间的一个数，然后返回这个数的下标
class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
l , r = 0 , n
while l <= r :
mid = l + (r-l)//2
toggle = guess(mid)
if toggle == 0:
return mid
if toggle == 1:
l = mid + 1
else:
r = mid - 1
Leetcode 367. Valid Perfect Square
给定一个数值，判断是不是Perfect Square，这里只需要从0到Target中选择折中点，然后不停乘方和Target比对即可，因为返回是Boolean，同样不需要考虑边界
class Solution:
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
l, r = 0, num
while l <= r:
mid = l + (r-l)//2
if mid ** 2 == num:
return True
if num > mid ** 2:
l = mid + 1
else:
r = mid - 1
return False
由于这一类题基本上就是套公式，直接考公式的几率很小。所以Medium以上的题目会对边界的选定模糊化，我们要做的是明确边界，然后再套公式。下面举例二分经典题：
33. Search in Rotated Sorted Array
取中间值以后会发现，左边或者右边，至少有一边是sorted的，根据这个特性，搭配下面这个神图，就能理解下一段的代码
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
l , r = 0, len(nums) - 1
while l <= r:
mid = l + (r-l)//2
if target == nums[mid]:
return mid
if nums[mid] >= nums[l]:
if nums[l] <= target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] <= target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1
第二类题：没有明确Target的题型
纳尼，你说你弄不懂到底返回left还是right，不慌，边界处理神器镇楼。
该神器的使用方法：把代码拷过去，然后initiatize一个object，随便传入一个Test Case，然后点运行。代码会一步一步的跑，你就可以看你left和right在每一层迭代之后的值了
这一类的题比较多变，可能会要你找
- 比Target大的最小值
- 比Target小的最大值
- 满足要求的第一个值
- 不满足要求的最后一个值
- …
在刷这类题前，我们先看看模板，在迭代退出的时候，left和right的位置：
Case 1:
Array = [1,2,3,5,6], Target = 4
首先这个程序肯定返回-1。我们的模板对While Loop定义如下：
while l <= r:
那么只有当l > r的时候，While Loop才会终止。
重点来了，当迭代结束后，假设Target为4， L和R的位置分别对应着两个条件：
L对应的是：第一个比4大的坐标, 根据这道题的定义就是比Target大的最小值
R对应的是：最后一个比4小的坐标，根据这道题的定义就是比Target小的最大值
Case 2:
Array = [1,2,3,5,6], Target = 7
根据我们While Loop的特性，有一个Edge的情况就是，L最大可以等于len(array)
这里可以看到，如果我们要返回array[l]，系统是会报错的，因为我们的L已经越界了，这个局限性是这套模板的小短板，当然，只要大家记住这一点，以后就可以写出相对应的Edge Case处理。
l 和 r 的位置和定义清楚了以后，我们来做做题。
返回l的情况： 33. Search in Rotated Sorted Array
给了一个Target值，找到在Array里，Target按顺序应该插入的位置。
class Solution:
def searchInsert(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r-l)//2
if nums[mid] == target:
return mid
if target > nums[mid]:
l = mid + 1
else:
r = mid - 1
return l
这里我们同样可以用镇楼法宝模拟下L,R在迭代结束后的下标
Input: [1,3,5,6], 2
Output: 1
l的下标是1， 定义是第一个满足条件的最小值。
r的下标是0，定义是最后一个不满足条件的最大值。
我们返回l 即可，另外还要说一点，这个模板对于这道题得天独厚的好处就是，不需要考虑当target插入的下标等于len(arr)的Edge Case，因为l本身就自带这个特性。
返回r的情况：458. Last Position of Target (Lintcode)
给了一个Target值，找到在Array里，该Target值出现最后的坐标
class Solution:
def lastPosition(self, nums, target):
if not nums:
return -1
l , r = 0 , len(nums) - 1
while l <= r:
mid = l + (r-l)//2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
if nums[r] == target:
return r
else:
return -1
这道题的Array里面会有重复，去重的方式就是当nums[mid] == target的时候，对left进行增值。这样就可以去掉左边重复的数。
举例：
Input: [1, 2, 2, 4, 5, 5]
target = 2, return 2
l的下标是3， 定义是第一个不满足条件的值
r的下标是2，定义是最后一个满足条件的值。
所以返回r
楼上两题的合体：34. Search for a Range
分别找到第一个位置，和最后一个位置，返回一个区间。
class Solution:
def searchRange(self, nums, target):
l = self.findLeft(nums, target)
r = self.findRight(nums, target)
return [l, r] if l <= r else [-1, -1]
def findLeft(self, nums, target):
l, mid, r = 0, 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return l
def findRight(self, nums, target):
l, mid, r = 0, 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
return r
第三类题：没有明确Target的题型，可越界类型
这种类型的题目，用 l <= r 的模板可能会越界，我们可以填写个别的Edge Case处理，或者套用其他比如 l < r 或者 l + 1 < r的模板解决。
162. Find Peak Element
找峰值，mid比对的区间是 nums[mid + 1]，这种情况当l 越界等于 len(nums)就会报错，所以可以选择用 while l + 1 < r的区间，最终对l和r进行比对。当然也可以写Edge处理。
class Solution:
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l , mid , r = 0, 0, len(nums) - 1
while l + 1 < r:
mid = l + (r-l)//2
if nums[mid] < nums[mid + 1]:
l = mid
else:
r = mid
if nums[l] > nums[r]: return l
else: return r
153. Find Minimum in Rotated Sorted Array
这道题最终要返回的nums[l]。同样，可以写Edge Case处理，也可以使用 while l < r 或者 while l + 1 < r来解。
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = l + (r - l) // 2
if nums[mid] > nums[r]:
l = mid
else:
r = mid
return min(nums[l], nums[r])