本文总结了二叉搜索的各类经典问题及解法，并进行了分类，代码片段中题目描述注释部分中紧接着题目后面方括号内的数字为该题在 LeetCode 题库中的编号，算法的说明随同附带在代码片段的注释之中，另外不做额外解释。
本文涉及的所有题目及实现代码下载链接为：http://xule.ren/wp-content/uploads/2018/03/LeetCode_binary_search.zip
标准库头文件 <algorithm> 中有 binary_search、lower_bound、upper_bound 和 equal_range 四个与二分查找有关的函数，lower_bound 返回升序数组中第一个大于等于给定值的元素下标，upper_bound 返回有序数组中第一个大于给定值的元素下标，equal_range 通过返回一个 pair 同时给出 lower_bound 和 upper_bound 的结果，不过效率比分别调用它们要稍微高一些。下面给出四种二分查找的变形函数，它们的功能分别是找出一个升序数组中第一个等于给定值的元素下标、最后一个等于给定值的元素下标、第一个大于给定值的元素下标、最后一个小于给定值的元素下标，若不存在，它们都返回 -1。
/* find the first element equals to target (lower_bound) */
int firstEqual(std::vector<int>& nums, int target)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] < target)
lo = mid + 1;
else
hi = mid;
}
return !nums.empty() && nums[lo] == target ? lo : -1;
}
/* find the last element equals to target */
int lastEqual(std::vector<int>& nums, int target)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo + 1 >> 1);
if (nums[mid] <= target)
lo = mid;
else
hi = mid - 1;
}
return !nums.empty() && nums[lo] == target ? lo : -1;
}
/* find the first element greater than target (upper_bound) */
int firstGreater(std::vector<int>& nums, int target)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] <= target)
lo = mid + 1;
else
hi = mid;
}
return !nums.empty() && nums[lo] > target ? lo : -1;
}
/* find the last element less than target */
int lastLess(std::vector<int>& nums, int target)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo + 1 >> 1);
if (nums[mid] < target)
lo = mid;
else
hi = mid - 1;
}
return !nums.empty() && nums[lo] < target ? lo : -1;
}
前两种变形都可用来作为二分查找的实现。对于在求 mid 的时候是应该向下取整还是向上取整，当查找满足某种条件的第一个元素时，向下取整，尽量往左边查找；当查找满足某种条件的最后一个元素时，向上取整，尽量往右边查找。在缩小查找区间的时候，确保待查找的元素不会落到缩小后的区间外边，直至区间中只存在一个元素时，即当 lo == hi 的时候，lo 就是待查找元素的下标。
Explicit
LeetCode 上有以下十二道看上去显式地与二分查找相关的题目
第 1 题：Sqrt(x)
/**
* 1. Sqrt(x) [69]
*
* Implement int sqrt(int x).
* Compute and return the square root of x.
* x is guaranteed to be a non-negative integer.
* @example
* Input: 4
* Output: 2
* @endexample
* @example
* Input: 8
* Output: 2
* Explanation: The square root of 8 is 2.82842..., and since we
* want to return an integer, the decimal part will be truncated.
* @endexample
*/
int mySqrt(int x)
{
int lo = 0, hi = x, mid = 0;
while (lo <= hi)
{
mid = lo + (hi - lo >> 1);
if (mid > 46340 || mid * mid > x) // 46340^2 < 2147483647 < 46341^2
hi = mid - 1;
else
lo = mid + 1;
}
return hi;
}
在 [0, x] 之间找到第一个平方是小于等于 x 的数即可。
第 2 题：Search Insert Position
/**
* 2. Search Insert Position [35]
*
* Given a sorted array and a target value, return the index if the target is found.
* If not, return the index where it would be if it were inserted in order.
* You may assume no duplicates in the array.
* @example
* Input: [1,3,5,6], 5
* Output: 2
* @endexample
* @example
* Input: [1,3,5,6], 2
* Output: 1
* @endexample
* @example
* Input: [1,3,5,6], 7
* Output: 4
* @endexample
* @example
* Input: [1,3,5,6], 0
* Output: 0
* @endexample
*/
int searchInsert(std::vector<int>& nums, int target)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] < target)
lo = mid + 1;
else if (nums[mid] > target)
hi = mid - 1;
else
return mid;
}
return lo;
}
第 3 题：Search for a Range
/**
* 3. Search for a Range [34]
*
* Given an array of integers sorted in ascending order, find the starting
* and ending position of a given target value.
* Your algorithm's runtime complexity must be in the order of O(log n).
* If the target is not found in the array, return [-1, -1].
* @example
* Given [5, 7, 7, 8, 8, 10] and target value 8,
* return [3, 4].
* @endexample
*/
std::vector<int> searchRange(std::vector<int>& nums, int target)
{
std::vector<int> res(2, -1);
if (nums.empty())
return res;
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
// search for the left one
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] < target)
lo = mid + 1;
else
hi = mid;
}
if (nums[lo] != target)
return res;
res[0] = lo;
// search for the right one
hi = static_cast<int>(nums.size()) - 1; // we don't have to set lo to 0 the second time.
while (lo < hi)
{
int mid = lo + (hi - lo + 1 >> 1); // make mid biased to the right
if (nums[mid] > target)
hi = mid - 1;
else
lo = mid; // so that this won't make the search range stuck.
}
res[1] = hi;
return res;
}
在查找到第一个等于给定值的元素后，不需要重新置 lo 为 0。
第 4 题：Search in Rotated Sorted Array
/**
* 4. Search in Rotated Sorted Array [33]
*
* Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
* (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
* You are given a target value to search. If found in the array return its index, otherwise return -1.
* You may assume no duplicate exists in the array.
*/
int search(std::vector<int>& A, int target)
{
int lo = 0, hi = static_cast<int>(A.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (A[mid] == target)
return mid;
if (A[mid] > A[hi]) // the first half [lo, mid] is in order
{
if (target >= A[lo] && target < A[mid])
hi = mid - 1;
else
lo = mid + 1;
}
else
{
if (target > A[mid] && target <= A[hi])
lo = mid + 1;
else
hi = mid - 1;
}
}
return !A.empty() && A[lo] == target ? lo : -1;
}
区间 [lo, mid] 有序时，若 target >= A[lo] && target < A[mid]，则 target 必然不会存在于 [mid, hi] 中，否则必然不会存在于 [lo, mid] 中。
第 5 题：Search in Rotated Sorted Array II
/**
* 5. Search in Rotated Sorted Array II [81]
*
* What if duplicates are allowed?
* Would this affect the run-time complexity? How and why?
* Suppose an array sorted in ascending order is rotated at
* some pivot unknown to you beforehand.
* Write a function to determine if a given target is in the array.
* The array may contain duplicates.
*/
bool search(std::vector<int>& A, int target)
{
int lo = 0, hi = static_cast<int>(A.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (A[mid] == target)
return true;
if (A[mid] > A[hi]) // the first half [lo, mid] is in order
{
if (target >= A[lo] && target < A[mid])
hi = mid;
else
lo = mid + 1;
}
else if (A[mid] < A[hi]) // the second half [mid, hi] is in order
{
if (target > A[mid] && target <= A[hi])
lo = mid + 1;
else
hi = mid;
}
else
--hi;
}
return !A.empty() && A[lo] == target;
}
第 6 题：Find Minimum in Rotated Sorted Array
/**
* 6. Find Minimum in Rotated Sorted Array [153]
*
* Suppose an array sorted in ascending order is rotated
* at some pivot unknown to you beforehand.
* (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
* Find the minimum element.
* You may assume no duplicate exists in the array.
*/
int findMin(std::vector<int>& nums)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] > nums[hi]) // the first half [lo, mid] is in order
lo = mid + 1;
else
hi = mid;
}
return nums[lo];
}
区间 [lo, mid] 有序表明最小值一定在 mid 右侧。
第 7 题：Find Minimum in Rotated Sorted Array II
/**
* 7. Find Minimum in Rotated Sorted Array II [154]
*
* What if duplicates are allowed?
* Would this affect the run-time complexity? How and why?
* Suppose an array sorted in ascending order is rotated
* at some pivot unknown to you beforehand.
* (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
* Find the minimum element.
* The array may contain duplicates.
*/
int findMin(std::vector<int>& nums)
{
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (nums[mid] > nums[hi]) // the first half [lo, mid] is in order
lo = mid + 1;
else if (nums[mid] < nums[hi]) // the second half [mid, hi] is in order
hi = mid;
else
--hi;
}
return nums[lo];
}
当 nums[mid] == nums[hi] 时，可能最小值在 [mid, hi] 之间，比如 [2,2,2,2,1,1,2]，第一次循环时，mid 为 3，hi 为6，因此不能直接把 hi 置为 mid，不断地 –hi 之后，若情况真如上述一样，则之后会在一次循环中进入 nums[mid] > nums[hi] 分支，即便是 [2,2,2,2,2,2,2] 的情况，不断地 –hi 之后也会因为 lo == hi 而退出 while 循环。
第 8 题：Find Peak Element
/**
* 8. Find Peak Element [162]
*
* A peak element is an element that is greater than its neighbors.
* Given an input array where num[i] != num[i+1],
* find a peak element and return its index.
* The array may contain multiple peaks, in that case
* return the index to any one of the peaks is fine.
* You may imagine that num[-1] = num[n] = -Inf.
* For example, in array [1, 2, 3, 1], 3 is a peak element
* and your function should return the index number 2.
* Note:
* Your solution should be in logarithmic complexity.
*/
/**
* We start off by finding the middle element, midmid from the given numsnums array.
* If this element happens to be lying in a descending sequence of numbers, or a local
* falling slope (found by comparing nums[i]nums[i] to its right neighbour), it means that
* the peak will always lie towards the left of this element. Thus, we reduce the search
* space to the left of midmid(including itself) and perform the same process on left subarray.
* If the middle element, midmid lies in an ascending sequence of numbers, or a rising slope
* (found by comparing nums[i]nums[i] to its right neighbour), it obviously implies that the
* peak lies towards the right of this element. Thus, we reduce the search space to the right
* of midmid and perform the same process on the right subarray.
* In this way, we keep on reducing the search space till we eventually reach a state where
* only one element is remaining in the search space. This single element is the peak element.
*/
int findPeakElement(std::vector<int>& nums)
{
int n = static_cast<int>(nums.size());
if (n < 2)
return 0;
int lo = 0, hi = n - 1, mid = 0;
while (lo < hi)
{
mid = lo + (hi - lo >> 1);
if (nums[mid] > nums[mid + 1])
hi = mid;
else // (nums[mid] < nums[mid + 1])
lo = mid + 1;
}
return lo;
}
第 9 题：H-Index II
/**
* 9. H-Index II [275]
*
* Follow up for H-Index: What if the citations array is sorted in ascending order?
* Could you optimize your algorithm?
*/
/**
* The basic idea of this solution is to use binary search to find the minimum index such that
* citations[index] >= length(citations) - index
* After finding this index, the answer is length(citations) - index.
* This logic is very similar to the C++ function lower_bound or upper_bound.
*/
int hIndex(std::vector<int>& citations)
{
int n = static_cast<int>(citations.size()), lo = 0, hi = n - 1;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (citations[mid] < n - mid)
lo = mid + 1;
else
hi = mid;
}
return n - lo;
}
第 10 题：First Bad Version
/**
* 10. First Bad Version [278]
*
* You are a product manager and currently leading a team to develop a new product.
* Unfortunately, the latest version of your product fails the quality check.
* Since each version is developed based on the previous version,
* all the versions after a bad version are also bad.
* Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one,
* which causes all the following ones to be bad.
* You are given an API bool isBadVersion(version) which will return
* whether version is bad. Implement a function to find the first bad version.
* You should minimize the number of calls to the API.
*/
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int firstBadVersion(int n)
{
int lo = 1, hi = n;
while (lo < hi)
{
int mid = lo + (hi - lo >> 1);
if (isBadVersion(mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
第 11 题：Guess Number Higher or Lower
/**
* 11. Guess Number Higher or Lower [374]
*
* We are playing the Guess Game. The game is as follows:
* I pick a number from 1 to n. You have to guess which number I picked.
* Every time you guess wrong, I'll tell you whether the number is higher or lower.
* You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
* -1 : My number is lower
* 1 : My number is higher
* 0 : Congrats! You got it!
* @example
* n = 10, I pick 6.
* Return 6.
* @endexample
*/
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
int guessNumber(int n)
{
int lo = 1, hi = n, mid = lo + (hi - lo >> 1), status = 0;
while ((status = guess(mid)) != 0)
{
if (status == 1)
lo = mid + 1;
else
hi = mid - 1;
mid = lo + (hi - lo >> 1);
}
return mid;
}
第 12 题：Median of Two Sorted Arrays
/**
* 12. Median of Two Sorted Arrays [4]
*
* There are two sorted arrays nums1 and nums2 of size m and n respectively.
* Find the median of the two sorted arrays.
* The overall run time complexity should be O(log (m+n)).
* @example
* nums1 = [1, 3]
* nums2 = [2]
* The median is 2.0
* @endexample
* @example
* nums1 = [1, 2]
* nums2 = [3, 4]
* The median is (2 + 3)/2 = 2.5
* @endexample
*/
/**
* First, let's see the concept of 'MEDIAN' in a slightly unconventional way.
* That is:
* "if we cut the sorted array to two halves of EQUAL LENGTHS, then
* median is the AVERAGE OF Max(lower_half) and Min(upper_half), i.e. the
* two numbers immediately next to the cut."
* For example, for [2 3 5 7], we make the cut between 3 and 5:
* [2 3 / 5 7]
* then the median = (3+5)/2. Note that I will use '/' to represent a cut,
* and (number / number) to represent a cut made through a number in this article.
* for [2 3 4 5 6], we make the cut right through 4 like this:
* [2 3 (4/4) 5 7]
* Since we split 4 into two halves, we say now both the lower and upper
* subarray contain 4. This notion also leads to the correct answer: (4 + 4) / 2 = 4;
* For convenience, let's use L to represent the number immediately left to the cut,
* and R the right counterpart. In [2 3 5 7], for instance, we have L = 3 and R = 5, respectively.
* We observe the index of L and R have the following relationship with the length of the array N:
* N Index of L / R
* 1 0 / 0
* 2 0 / 1
* 3 1 / 1
* 4 1 / 2
* 5 2 / 2
* 6 2 / 3
* 7 3 / 3
* 8 3 / 4
* It is not hard to conclude that index of L = (N-1)/2, and R is at N/2.
* Thus, the median can be represented as
* (L + R)/2 = (A[(N-1)/2] + A[N/2])/2
*
* To get ready for the two array situation, let's add a few imaginary
* 'positions' (represented as #'s) in between numbers, and treat
* numbers as 'positions' as well.
* [6 9 13 18] -> [# 6 # 9 # 13 # 18 #] (N = 4)
* position index 0 1 2 3 4 5 6 7 8 (N_Position = 9)
* [6 9 11 13 18]-> [# 6 # 9 # 11 # 13 # 18 #] (N = 5)
* position index 0 1 2 3 4 5 6 7 8 9 10 (N_Position = 11)
* As you can see, there are always exactly 2*N + 1 'positions' regardless of length N.
* Therefore, the middle cut should always be made on the Nth position (0-based).
* Since index(L) = (N-1)/2 and index(R) = N/2 in this situation,
* we can infer that index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2.
*
* Now for the two-array case:
* A1: [# 1 # 2 # 3 # 4 # 5 #] (N1 = 5, N1_positions = 11)
* A2: [# 1 # 1 # 1 # 1 #] (N2 = 4, N2_positions = 9)
* Similar to the one-array problem, we need to find a cut that divides
* the two arrays each into two halves such that
* "any number in the two left halves" <= "any number in the two right halves".
* We can also make the following observations：
* 1. There are 2N1 + 2N2 + 2 position altogether. Therefore, there must be exactly
* N1 + N2 positions on each side of the cut, and 2 positions directly on the cut.
* 2. Therefore, when we cut at position C2 = K in A2, then the cut position in A1
* must be C1 = N1 + N2 - k. For instance, if C2 = 2, then we must have
* C1 = 4 + 5 - C2 = 7.
* [# 1 # 2 # 3 # (4/4) # 5 #]
* [# 1 / 1 # 1 # 1 #]
* 3. When the cuts are made, we'd have two L's and two R's. They are
* L1 = A1[(C1-1)/2]; R1 = A1[C1/2];
* L2 = A2[(C2-1)/2]; R2 = A2[C2/2];
*
* Now how do we decide if this cut is the cut we want? Because L1, L2 are the greatest
* numbers on the left halves and R1, R2 are the smallest numbers on the right, we only need
* L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2
* to make sure that any number in lower halves <= any number in upper halves.
* As a matter of fact, since L1 <= R1 and L2 <= R2 are naturally guaranteed
* because A1 and A2 are sorted, we only need to make sure:
* L1 <= R2 and L2 <= R1.
* Now we can use simple binary search to find out the result.
* 1. If we have L1 > R1, it means there are too many large numbers on the left half of A1,
* then we must move C1 to the left (i.e. move C2 to the right);
* 2. If L2 > R1, then there are too many large numbers on the left half of A2,
* and we must move C2 to the left.
* 3. Otherwise, this cut is the right one.
* After we find the cut, the medium can be computed as (max(L1, L2) + min(R1, R2)) / 2;
* Two side notes:
* A. Since C1 and C2 can be mutually determined from each other, we can just move
* one of them first, then calculate the other accordingly. However, it is much
* more practical to move C2 (the one on the shorter array) first. The reason is
* that on the shorter array, all positions are possible cut locations for median,
* but on the longer array, the positions that are too far left or right are simply
* impossible for a legitimate cut. For instance, [1], [2 3 4 5 6 7 8]. Clearly
* the cut between 2 and 3 is impossible, because the shorter array does not have
* that many elements to balance out the [3 4 5 6 7 8] part if you make the cut
* this way. Therefore, for the longer array to be used as the basis for the first
* cut, a range check must be performed. It would be just easier to do it on the
* shorter array, which requires no checks whatsoever. Also, moving only on the
* shorter array gives a run-time complexity of O(log(min(N1, N2)))
* B. The only edge case is when a cut falls on the 0th(first) or the 2Nth(last) position.
* For instance, if C2 = 2N2, then R2 = A2[2*N2/2] = A2[N2], which exceeds the
* boundary of the array. To solve this problem, we can imagine that both A1 and A2
* actually have two extra elements, INT_MAX at A[-1] and INT_MAX at A[N].
* These additions don't change the result, but make the implementation easier:
* If any L falls out of the left boundary of the array, then L = INT_MIN,
* and if any R falls out of the right boundary, then R = INT_MAX.
*/
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2)
{
int N1 = static_cast<int>(nums1.size()), N2 = static_cast<int>(nums2.size());
if (N1 < N2) return findMedianSortedArrays(nums2, nums1); // Make sure A2 is the shorter one.
int lo = 0, hi = 2 * N2;
while (lo <= hi)
{
int mid2 = lo + (hi - lo >> 1); // Try Cut 2
int mid1 = N1 + N2 - mid2; // Calculate Cut 1 accordingly
double L1 = (mid1 > 0) ? nums1[(mid1-1)/2] : INT_MIN; // Get L1, R1, L2, R2 respectively
double L2 = (mid2 > 0) ? nums2[(mid2-1)/2] : INT_MIN;
double R1 = (mid1 < 2*N1) ? nums1[(mid1)/2] : INT_MAX;
double R2 = (mid2 < 2*N2) ? nums2[(mid2)/2] : INT_MAX;
if (L1 > R2)
lo = mid2 + 1; // A1's lower half is too big; need to move C1 left (C2 right)
else if (L2 > R1)
hi = mid2 - 1; // A2's lower half too big; need to move C2 left.
else
return (std::max(L1, L2) + std::min(R1, R2)) / 2; // Otherwise, that's the right cut.
}
return -1.0;
}
Matrix
LeetCode 上有以下三道在矩阵中进行二分查找的题目
第 1 题：Search a 2D Matrix
/**
* 1. Search a 2D Matrix [74]
*
* Write an efficient algorithm that searches for a value in an m x n matrix.
* This matrix has the following properties:
* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.
* @example
* Consider the following matrix:
* [
* [1, 3, 5, 7],
* [10, 11, 16, 20],
* [23, 30, 34, 50]
* ]
* Given target = 3, return true.
* @endexample
*/
/**
* m * n matrix convert to an array => matrix[x][y] => a[x * n + y]
* an array convert to m * n matrix => a[x] => matrix[x / n][x % n]
*/
bool searchMatrix(std::vector<std::vector<int> >& matrix, int target)
{
if (matrix.empty() || matrix[0].empty())
return false;
int m = static_cast<int>(matrix.size()), n = static_cast<int>(matrix[0].size());
int lo = 0, hi = m * n - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo >> 1);
if (matrix[mid / n][mid % n] < target)
lo = mid + 1;
else if (matrix[mid / n][mid % n] > target)
hi = mid - 1;
else
return true;
}
return false;
}
转换成一维数组即可。
第 2 题：Search a 2D Matrix II
/**
* 2. Search a 2D Matrix II [240]
*
* Write an efficient algorithm that searches for a value in an m x n matrix.
* This matrix has the following properties:
* Integers in each row are sorted in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.
* @example
* [
* [ 1, 4, 7, 11, 15],
* [ 2, 5, 8, 12, 19],
* [ 3, 6, 9, 16, 22],
* [10, 13, 14, 17, 24],
* [18, 21, 23, 26, 30]
* ]
* Given target = 5, return true.
* Given target = 20, return false.
* @endexample
*/
bool searchMatrix(std::vector<std::vector<int> >& matrix, int target)
{
if (matrix.empty() || matrix[0].empty())
return false;
int m = static_cast<int>(matrix.size()), n = static_cast<int>(matrix[0].size());
int i = 0, j = n - 1;
while (i < m && j >= 0)
{
if (matrix[i][j] < target)
++i;
else if (matrix[i][j] > target)
--j;
else
return true;
}
return false;
}
从右上角的元素开始，若该元素比给定值大，则向左搜索，因为该元素已经是最后一列中最小的元素了，否则向下搜索，当向左不断 –j 时只要不是 matrix[0][0] > target，则总会到了某一列的时候 matrix[i][j] < target，然后一直向下搜索，该算法的时间复杂度为 O(m+n)，当矩阵中仅有 matrix[m-1][0] == target 时是最差的情况。
第 3 题：Kth Smallest Element in a Sorted Matrix
/**
* 3. Kth Smallest Element in a Sorted Matrix [378]
*
* Given a n x n matrix where each of the rows and columns are sorted
* in ascending order, find the kth smallest element in the matrix.
* Note that it is the kth smallest element in the sorted order,
* not the kth distinct element.
* @example
* matrix = [
* [ 1, 5, 9],
* [10, 11, 13],
* [12, 13, 15]
* ],
* k = 8,
* return 13.
* @endexample
* Note:
* You may assume k is always valid, 1 <= k <= n^2.
*/
int kthSmallest(std::vector<std::vector<int> >& matrix, int k)
{
int n = static_cast<int>(matrix.size()), lo = matrix[0][0], hi = matrix[n-1][n-1];
while (lo < hi)
{
int mid = lo + (hi - lo >> 1), index = 0;
for (int i = 0; i < n; ++i)
index += std::upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
if (index < k)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
Implicit
LeetCode 上有以下三道隐式地与二分查找相关的题目
第 1 题：Longest Increasing Subsequence
/**
* 1. Longest Increasing Subsequence [300]
*
* Given an unsorted array of integers, find the length of longest increasing subsequence.
* @example
* Given [10, 9, 2, 5, 3, 7, 101, 18],
* The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
* @endexample
* Note that there may be more than one LIS combination, it is only necessary for you
* to return the length. Your algorithm should run in O(n^2) complexity.
* Follow up:
* Could you improve it to O(n log n) time complexity?
*/
/** http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ */
int lengthOfLIS(std::vector<int>& nums)
{
std::vector<int> Y;
if (nums.empty())
return 0;
int n = static_cast<int>(nums.size()), i = 0, j = 0, L = 0;
std::vector<int> g(n, 2147483647);
for (i = 0; i < n; ++i)
{
j = std::lower_bound(g.begin(), g.begin()+i+1, nums[i]) - g.begin();
g[j] = nums[i];
if (L < j + 1)
{
L = j + 1;
Y = g;
}
}
return L;
}
第 2 题：Split Array Largest Sum
/**
* 2. Split Array Largest Sum [410]
*
* Given an array which consists of non-negative integers and an integer m,
* you can split the array into m non-empty continuous subarrays.
* Write an algorithm to minimize the largest sum among these m subarrays.
* @example
* Input:
* nums = [7,2,5,10,8]
* m = 2
* Output:
* 18
* Explanation:
* There are four ways to split nums into two subarrays.
* The best way is to split it into [7,2,5] and [10,8],
* where the largest sum among the two subarrays is only 18.
* @endexample
* Note:
* If n is the length of array, assume the following constraints are satisfied:
* 1. 1 <= n <= 1000;
* 2. 1 <= m <= min(50, n).
*/
/**
* Introduction to this problem:
* We can break this problem into two smaller problems:
* 1. Given an array (A), number of cuts (CUTS), and the Largest sum of
* sub-arrays (MAX). Can you use at most CUTS cuts to segment array A
* into CUTS + 1 sub-arrays, such that the sum of each sub-array is
* smaller or equal to MAX?
* 2. Given a lower bound (left), an upper bound (right), an unknown
* bool array (B), and an API uses i as input and tells you whether B[i]
* is true. If we know there exists an index k, that B[i] is false when
* i < k, and B[i] is true when i >= k. What is the fastest way to find
* this k (the lower bound)?
*
* Solution to the first sub-problem
* For the first question, we can follow these steps:
* 1. For each element in the array, if its value is larger than MAX, we know
* it's not possible to cut this array into groups that the sum of all groups
* are smaller than MAX. (Reason is straightforward, if A is [10, 2, 3, 5]
* and MAX is 6, even you have 3 cuts by which you can cut A as
* [[10], [2], [3], [5]], the group containing 10 will still be larger than 6).
* 2. Use greedy algorithm to cut A. Use an accumulator sum to store the sum of
* the currently processed group, and process elements in A one by one.
* For each element num, if we add num with sum and the new sum is still
* no larger than MAX, we update sum to sum + num, which means we can merge
* num into the current group. If not, we must use a cut before num to
* segment this array, then num will be the first element in the new group.
* 3. If we didn’t go through A but already used up all cuts, then it's not
* possible only using CUTS cuts to segment this array into groups to make sure
* sum of each sub-array is smaller than MAX. Otherwise, if we can reach the
* end of A with cuts left (or use exactly CUTS cuts). It’s possible to do so.
* Then the first question is solved.
*
* Solution to the second sub-problem
* 1. The array B will be something like [false, ..., false, true, true, ..., true].
* We want to find the index of the first true.
* 2. Use binary search to find this k. Keep a value mid, mid = (left + right) / 2.
* If B[mid] = false, then move the search range to the upper half of the
* original search range, a.k.a left = mid + 1, otherwise move search range to
* the lower half, a.k.a right = mid.
*
* Why this algorithm is correct...
* 1. No matter how we cut the array A, the Largest sum of sub-arrays will fall
* into a range [left, right]. Left is the value of the largest element in this
* array. right is the sum of this array. (e.g., Given array [1, 2, 3, 4, 5],
* if we have 4 cuts and cut it as [[1], [2], [3], [4], [5]], the Largest sum
* of sub-arrays is 5, it cannot be smaller. And if we have 0 cut, and the
* only sub-array is [[1, 2, 3, 4, 5]], the Largest sum of sub-arrays is 15,
* it cannot be larger).
* 2. However, we cannot decide the number of cuts (CUTS), this is an given
* constraint. But we know there must be a magic number k, which is the smallest
* value of the Largest sum of sub-arrays when given CUTS cuts. When the Largest
* sum of sub-arrays is larger than k, we can always find a way to cut A within
* CUTS cuts. When the Largest sum of sub-arrays is smaller than k, there is
* no way to do this.
*
* For example, given array A [1, 2, 3, 4, 5]. We can use 2 cuts.
* 1. No matter how many cuts are allowed, the range of the possible value of the
* Largest sum of sub-arrays is [5, 15].
* 2. When given 2 cuts, we can tell the magic number k here is 6, the result of
* segmentation is [[1, 2, 3], [4], [5]].
* 3. When Largest sum of sub-arrays is in range [6, 15], we can always find a way
* to cut this array within two cuts. You can have a try.
* 4. However, when Largest sum of sub-arrays is in range [5, 5], there is no way
* to do this.
* 5. This mapped this problem into the second sub-problem. Bool array B here is
* [5:false, 6:true, 7:true, 8:true, ..., 15:true]. We want to find the index i
* of the first true in B, which is the answer of this entire question, and by
* solving the first sub-problem, we have an API that can tell us given an i
* (Largest sum of sub-arrays), whether B[i] is true (whether we can find a way
* to cut A to satisfy the constraint).
*/
class Solution
{
public:
int splitArray(std::vector<int>& nums, int m)
{
int64_t lo = 0, hi = 0;
for (size_t i = 0; i < nums.size(); ++i)
{
if (lo < nums[i])
lo = nums[i];
hi += nums[i];
}
while (lo < hi)
{
int64_t mid = lo + hi >> 1;
if (cutable(nums, m-1, mid))
hi = mid;
else
lo = mid + 1;
}
return lo;
}
private:
bool cutable(std::vector<int>& nums, int cuts, int64_t max)
{
int64_t sum = 0;
for (size_t i = 0; i < nums.size(); ++i)
{
sum += nums[i];
if (sum > max)
{
if (--cuts < 0)
return false;
sum = nums[i];
}
}
return true;
}
};
第 3 题：Preimage Size of Factorial Zeroes Function
/**
* 3. Preimage Size of Factorial Zeroes Function [793]
*
* Let f(x) be the number of zeroes at the end of x!. (Recall that
* x! = 1 * 2 * 3 * ... * x, and by convention, 0! = 1.)
* For example, f(3) = 0 because 3! = 6 has no zeroes at the end,
* while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end.
* Given K, find how many non-negative integers x have the
* property that f(x) = K.
* @example
* Input: K = 0
* Output: 5
* Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.
* @endexample
* @example
* Input: K = 5
* Output: 0
* Explanation: There is no x such that x! ends in K = 5 zeroes.
* @endexample
* Note:
* K will be an integer in the range [0, 10^9].
*/
class Solution
{
public:
int preimageSizeFZF(int K)
{
return kZerosAtLeast(K+1) - kZerosAtLeast(K);
}
private:
int kZerosAtLeast(int64_t K)
{
int64_t lo = 0, hi = K * 10;
while (lo < hi)
{
int64_t mid = lo + (hi - lo >> 1);
int64_t zeroes = trailingZeroes(mid);
if (zeroes < K)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
int64_t trailingZeroes(int64_t n)
{
return n < 5 ? 0 : n/5 + trailingZeroes(n/5);
}
};