binary search 总结

二分法比较简单, 时间复杂度为O(log n)
mid = right + (left - right) / 2 防止left right 都大时候溢出
两种二分法
1. start <= end 每次start = mid + 1 或者 end = mid - 1
2. start + 1 < end 每次 start = mid 或者 end = mid

正常情况下用1的方法, 但是如果mid+1 或者mid-1 可能会错过target的话(mid 为target) 例如Find Minimum in Rotated Sorted Array 用方法2

Search for a Range

Search Insert Position

Sqrt(x)

Search in Rotated Sorted Array

Search in Rotated Sorted Array II

前边的题只需要mid 跟target比较 而这两道题则还需要跟左右边界比较 所以要注意跟边界相等的情况下不仅会出现 > < 还有>= <=


Find Minimum in Rotated Sorted Array

与之前不同的是如果这道题每次 Amid < A[right] -->mid - 1 = right 的话那么 可能会出现如果此时mid是最小值 但是右边界确实最大值 为了防止这种情况 每次left right 都取 mid 而不是mid +-1 但是这么取得话就不能用left <= right 了 否则会无限循环 所以这里用left + 1 < right
Find Minimum in Rotated Sorted Array II

Search a 2D Matrix