待補(bǔ)充。
Leetcode上Binary Search題目（按frequency排序）：
4 Median of Two Sorted Arrays
50 Pow(x, n)
153 Find Minimum in Rotated Sorted Array
33 Search in Rotated Sorted Array
69 Sqrt(x)
29 Divide Two Integers
162 Find Peak Element
278 First Bad Version
34 Search for a Range
35 Search Insert Position
74 Search a 2D Matrix
240 Search a 2D Matrix II
154 Find Minimum in Rotated Sorted Array II
81 Search in Rotated Sorted Array II
222 Count Complete Tree Nodes
287 Find the Duplicate Number
230 Kth Smallest Element in a BST
209 Minimum Size Subarray Sum
174 Dungeon Game
300 Longest Increasing Subsequence
275 H-Index II
167 Two Sum II - Input array is sorted
270 Closest Binary Search Tree Value
302 Smallest Rectangle Enclosing Black Pixels
本文題目目錄：
1.search-a-2d-matrix
2.search-for-a-range
3.sqrtx
4.search-insert-position
5.find-minimum-in-rotated-sorted-array
6.find-minimum-in-rotated-sorted-array-ii
7.search-in-rotated-sorted-array
8.search-in-rotated-sorted-array-ii
9.find-peak-element
訣竅：
永遠(yuǎn)返回l法。初始的l和r取可能的最左(含)和最右(含)贷笛。永遠(yuǎn)讓l處于可能為結(jié)果的那個(gè)位置(這樣r自然也處于)宙项。l = m的時(shí)候m = (l+r)/2+1, l = m+1的時(shí)候m = (l+r)/2。
如果發(fā)現(xiàn)不對(duì)的地方歡迎指正汇荐。
1.search a 2d matrix
l = mid+1而非mid盆繁，否則會(huì)陷入死循環(huán)。<target的時(shí)候革娄，target只有可能在mid+1開(kāi)始的地方秕狰，不可能為mid鸣哀，所以l=mid+1。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) return false;
int m = matrix.size();
int n = matrix[0].size();
int l = 0;
int r = m * n - 1;
int x,y;
while(l < r) {
int mid = l + (r - l) / 2;
x = mid/n;
y = mid%n;
if(matrix[x][y] < target) {
l = mid + 1;
} else {
r = mid;
}
}
x = l/n;
y = l%n;
return matrix[x][y] == target;
}
};
2.search for a range
找左側(cè)：if(A[m]<target) 目標(biāo)肯定在m+1往后（含）
找右側(cè)：if(A[m]<=target) 目標(biāo)肯定在m往后（含）叹放，l=m挠羔，所以m要+1，否則死循環(huán)
class Solution {
public:
vector<int> searchRange(vector<int>& A, int target) {
int n = A.size();
int lres,rres;
//find lres
int l = 0;
int r = n - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(A[m] < target) {
l = m + 1;
} else {
r = m;
}
}
lres = l;
if(A[lres] != target) {
return {-1, -1};
}
//find rres
l = 0;
r = n - 1;
while(l < r) {
int m = l + (r - l) / 2 + 1;
if(A[m] <= target) {
l = m;
} else {
r = m - 1;
}
}
rres = l;
return {lres, rres};
}
};
3.sqrtx
類似上一題的find rres俱恶。
if(m <= x/m) 那么目標(biāo)肯定在m往右（含）合是，所以m要+1，l=m
class Solution {
public:
int mySqrt(int x) {
int l = 0;
int r = x;
while(l < r) {
int m = l + (r - l) / 2 + 1;
if(m <= x/m) {
l = m;
} else {
r = m - 1;
}
}
return l;
}
};
4.search insert position
初始化的時(shí)候注意泊藕，最左可能為0难礼，最右可能為n而不是n-1。
注意題意在nums[m] ==target時(shí)插入在m的位置讼呢。如果要插入到后面谦炬，就要讓if(nums[m] < target)改為<=。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int l = 0;
int r = n;
while(l < r) {
int m = l + (r - l)/2;
if(nums[m] < target) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
};
5.find minimum in rotated sorted array
類似上面，比較簡(jiǎn)單散劫。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0;
int r = n - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(nums[m] < nums[r]) {
r = m;
} else {
l = m + 1;
}
}
return nums[l];
}
};
6.find minimum in rotated sorted array ii
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(n == 0) return -1;
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(nums[m] > nums[r]) {
l = m + 1;
} else if(nums[m] < nums[r]){
r = m;
} else {
r--;
}
}
return nums[l];
}
};
改進(jìn)else里面：
if(nums[l] < nums[m])
r = m - 1;
else if(nums[l] > nums[m])
r = m;
else
r--;
7.search in rotated sorted array
思路1获搏，直接做。思路2纬乍，先找到pivot裸卫，再做普通搜索（略）。
思路1：
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(nums[m] > nums[r]) {
if(target >= nums[l] && target <= nums[m]) {
r = m;
} else {
l = m + 1;
}
} else if(nums[m] < nums[r]) {
if(target > nums[m] && target <= nums[r]) {
l = m + 1;
} else {
r = m;
}
}
}
if(nums[l] == target)
return l;
return -1;
}
};
8.search in rotated sorted array ii
懶惰解法：
直接在上面的解法下面加一個(gè)else r--。內(nèi)部加一個(gè)判斷減少循環(huán)次數(shù)聋袋。
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(nums[m] == target) return true;
if(nums[m] > nums[r]) {
if(target >= nums[l] && target <= nums[m]) {
r = m;
} else {
l = m + 1;
}
} else if(nums[m] < nums[r]) {
if(target > nums[m] && target <= nums[r]) {
l = m + 1;
} else {
r = m;
}
} else {
r--;
}
}
return nums[l] == target;
}
};
9.Find Peak Element
返回隨意一個(gè)的程序如下幽勒。如果讓我找最左側(cè)的那個(gè)呢？只能順序找锈颗。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2;
if(nums[m] < nums[m+1]) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
};
