When to use binary search:
* 我们知道解空间在一个区间 [i,j]
* valid解是解空间的一个点（也可以看作是只有一个点的range）或者一个range的起始点或者结束点
* range之外的点都不是valid解
想法一般都两种：
* 直接找到解 （比如classical binary search)
* 找中间一个点，验证这个点，通过验证结果能知道valid解在左边或者右边区间
Template:
int binarySearchTemplate() { int i = [lower_bound_of_solution], j = [upper_bound_of_solution]; // valid range is [i,j] // while (i + 1 < j) { // Overflow if i is INT_MAX while (i < j - 1) { int m = i + (j - i) / 2; if (m is valid solution) return m; else if (solution is on left side) // valid range will be [i,m-1] or [i,m] j = m - 1, or m; else // valid range will be [m,j] or [m+1,j] i = m + 1, or m; } // now check if i or j is valid solution }
457. Classical Binary Search https://www.lintcode.com/en/problem/classical-binary-search/
class Solution { public: /* * @param nums: An integer array sorted in ascending order * @param target: An integer * @return: An integer */ int findPosition(vector<int> &nums, int target) { if (nums.size() == 0) return -1; int i = 0, j = nums.size()-1; // [i,j] is the all valid range while (i+1 < j) { // Loop will break if there're 1 or 2 items left int m = i + (j - i) / 2; if (nums[m] == target) return m; else if (target > nums[m]) i = m + 1; else j = m - 1; } if (nums[i] == target) // We need to check if i or j (i and j might be same) is valid return i; else if (nums[j] == target) return j; else return -1; } };
35. Search Insert Position https://leetcode.com/problems/search-insert-position/description/
class Solution { public: int searchInsert(vector<int>& nums, int target) { int i = 0, j = nums.size(); // valid range is [0,nums.size()] while (i+1 < j) { int m = i + (j - i) / 2; if (nums[m] == target) return m; else if (target > nums[m]) i = m + 1; // if target > nums[m], valid range will be [m+1,j] else j = m; // if target < nums[m], vlaid range will be [i,m] } if (target <= nums[i]) // only if target <= nums[i], result will be i; otherwise j. return i; return j; } };
69. Sqrt(x) https://leetcode.com/problems/sqrtx/description/
class Solution { public: int mySqrt(int x) { int i = 0, j = x; // valid range is [0,x] while (i + 1 < j) { long m = i + (j - i) / 2; if (m * m == x) return m; else if (m * m > x) // if target < m*m, valid range will be [i,m-1] j = m - 1; else // if target > m*m, valid range will be [m,j] i = m; } if (j * j <= x) // j is valid only when j*j <= x return j; return i; } };
34. Search for a Range https://leetcode.com/problems/search-for-a-range/description/
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if (nums.size() == 0) return vector<int>( { -1, -1} ); int low = -1; int i = 0, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[m] == target) j = m; else if (nums[m] > target) j = m - 1; else i = m + 1; } if (nums[i] == target) low = i; else if (nums[j] == target) low = j; if (low == -1) return vector<int>( { -1, -1} ); i = low, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[m] == target) i = m; else if (nums[m] > target) j = m - 1; // else // i = m + 1; // should never happen } if (nums[j] == target) return vector<int>( { low, j} ); else return vector<int>( { low, i} ); } };
33. Search in Rotated Sorted Array https://leetcode.com/problems/search-in-rotated-sorted-array/description/
class Solution { public: int search(vector<int>& nums, int target) { if (nums.size() == 0) return -1; int i = 0, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[m] == target) return m; else if (nums[i] < nums[m]) { if (nums[i] <= target && target < nums[m]) j = m - 1; else i = m + 1; } else { if (nums[m] < target && target <= nums[j]) i = m + 1; else j = m - 1; } } if (nums[i] == target) return i; else if (nums[j] == target) return j; return -1; } };
81. Search in Rotated Sorted Array II https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/
class Solution { public: bool search(vector<int>& nums, int target) { if (nums.size() == 0) return false; int i = 0, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[m] == target) return true; else if (nums[i] < nums[m]) { if (nums[i] <= target && target < nums[m]) j = m - 1; else i = m + 1; } else if (nums[i] > nums[m]) { if (nums[m] < target && target <= nums[j]) i = m + 1; else j = m - 1; } else { // nums[i] == nums[m] i++; } } return (nums[i] == target || nums[j] == target); } };
153. Find Minimum in Rotated Sorted Array https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
class Solution { public: int findMin(vector<int>& nums) { if (nums.size() == 0) return -1; int i = 0, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[i] < nums[j]) // not rotated return nums[i]; else if (nums[i] < nums[m]) i = m + 1; else j = m; } return min(nums[i], nums[j]); } };
154. Find Minimum in Rotated Sorted Array II https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
class Solution { public: int findMin(vector<int>& nums) { if (nums.size() == 0) return -1; int i = 0, j = nums.size()-1; while (i + 1 < j) { int m = i + (j - i) / 2; if (nums[i] < nums[j]) return nums[i]; if (nums[i] < nums[m]) i = m + 1; else if (nums[i] > nums[m]) j = m; else i++; } return min(nums[i], nums[j]); } };
278. First Bad Version https://leetcode.com/problems/first-bad-version/description/
// Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int i = 1, j = n; while (i < j - 1) { int m = i + (j - i) / 2; if (isBadVersion(m)) j = m; else i = m+1; } return isBadVersion(i) ? i : j; } };
378. Kth Smallest Element in a Sorted Matrix https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
class Solution { public: int m, n; int kthSmallest(vector<vector<int>>& matrix, int k) { m = matrix.size(); n = matrix[0].size(); int i = matrix[0][0], j = matrix[m-1][n-1]; while (i < j - 1) { int m = i + (j - i) / 2; int mc = getSmallerEqualCount(matrix, m); if (mc >= k) j = m; else i = m + 1; } return getSmallerEqualCount(matrix, i) >= k ? i : j; } int getSmallerEqualCount(vector<vector<int>>& matrix, int v) { int res = 0; for (int i = 0; i < m; i++) { auto it = upper_bound(matrix[i].begin(), matrix[i].end(), v); res += it - matrix[i].begin(); } return res; } };