首页 > 代码库 > Binary Search 模板以及例题 (=target, >target, >=target)
Binary Search 模板以及例题 (=target, >target, >=target)
根据Jikai Tang的网站和视频总结如下,
http://www.tangjikai.com/algorithms/leetcode-binary-search
1. 在sorted array里面找一个特定的数。
1 def bsearch(array, l, r, target): 2 while l <= r: 3 mid = l + (r - l) / 2 4 5 if array[mid] > target: 6 r = mid - 1 7 elif array[mid] < target: 8 l = mid + 1 9 else: 10 return mid 11 12 return -1
由于left和right可以相等,所以L2使用的是while l <= r。L3中的mid = l + (r-l)/2 比 mid = (l + r)/2 稍微好一点,原因是这样不会出现 l + r 太大导致溢出的情况。
例题 L167 two sum II sorted array
http://www.cnblogs.com/lettuan/p/6168439.html
Leetcode 74, 240 search in 2D matrix
http://www.cnblogs.com/lettuan/p/6213470.html
2. 找sorted array中第一个严格大于(或者大于等于) target的数。
1 def findUpperBound(array, l, r, target): 2 while l < r: 3 mid = l + (r - l) / 2 4 5 if array[mid] > target: 6 r = mid 7 else: 8 l = mid + 1 9 10 return l
首先注意模板中的L6, 如果array[mid] > target,这是mid完全有可能是第一个严格大于target的数,所以r只能挪到mid,而不能挪到mid-1. 而且L2中必须用 l<r,如果写成了l<=r。那么到上图中的step4之后,mid = l = r ,然后array[mid] > target,循环就无法结束。
寻找第一个大于等于target的题目模板几乎一样,只不过L6换成>=即可。
例题 Leetcode 35. Search Insert Position
http://www.cnblogs.com/lettuan/p/6367232.html
Leetcode 278. First Bad Version
http://www.cnblogs.com/lettuan/p/6182794.html
Binary Search 模板以及例题 (=target, >target, >=target)