题目
思路
1. 二分法总体不难, 但是在边界问题的处理上需要格外的小心
2. 上面的题目都是二分查找问题的变形, 要么是二分查找配合 int 特性(1/2 = 0), 要么是利用二分查找的原理来查找
3. 第一题和第三题是等价的, 都是查找一个数在排序数组中的最左出现位置和最右出现位置.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 |
class
Solution {public: vector<int> searchRange(int
A[], int
n, int
target) { int
left = left_pos(A, 0, n-1, target); int
right = right_pos(A, 0, n-1, target); if(left < 0 || left >= n || A[left] != target) { left = right = -1; } vector<int> res; res.push_back(left); res.push_back(right); return
res; } int
left_pos(int
A[], int
m, int
n, int
target) { if(m > n) return
m; int
mid = (m+n)>>1; // when a[mid] == target, prefer left one if(A[mid] >= target) { return
left_pos(A, m, mid-1, target); }else{ return
left_pos(A, mid+1, n, target); } } int
right_pos(int
A[], int
m, int
n, int
target) { if(m > n) return
n; int
mid = (m+n)>>1; //cout << mid << endl; // when a[mid] == target, prefer right one if(A[mid] > target) { return
right_pos(A, m, mid-1, target); }else{ return
right_pos(A, mid+1, n, target); } }}; |
在取最左位置时, 返回 low, 最右位置返回 high.
返回 low 或 high 是由 a[mid] == target 时递归的走向决定的.
取最左位置时, 当 low > high 时退出递归, 假设上一步是 a[mid] == target, 那么上一步的递归走向是 left_pos(A, low, mid-1, target)
mid-1 越界, 所以应当返回 low
4. 旋转数组中的最小数字. 这道题考察的是二分法原理.
考虑旋转数组二分查找的原理和以之构建的框架... OK
二分查找递归的方向由 a[mid] 和 target 的关系决定 :
b_search(mid+1, high, target) if(a[mid] >= target)
b_search(low, mid-1, target) if(a[mid] < target)
在旋转数组中, 当出现重复元素时, 假如 a[mid] == target, 递归函数的走向不明, 因此不能再使用二分查找了
5. 第四题算是 LIS 的子过程.
当 a[mid] == target , 直接返回 mid
递归函数结束时, return low: 函数结束意味着 low > high, 应该返回较大的 low.
二分法最简单的记法:
若 a[mid] == target 时返回 mid, 那么最终结果返回 low
否则, 最终结果按照思路 3 的分析进行
6. 第五题和第八题是二分法的变形. 第五题要注意, 每次进行二分至少要消去一行. 而第八题是从右上角, 每次消去一行
7. 第六七题利用到了 int 的性质, int 除以 2 不会有小数产生, 保证结果肯定会收敛. 其中第七题每次假设第 k 小数为 x, 这种设置方法与最大值最小化问题非常类似
原文：http://www.cnblogs.com/zhouzhuo/p/3618239.html