首页 > 代码库 > 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)