【LeetCode】二分查找

给一个升序数组，找到目标值在数组中的起始和结束位置，时间复杂度为 O(log n)。

e.g.

给定数组 [5, 7, 7, 8, 8, 10] 和目标值 8，返回 [3, 4]。若目标值不在数组中，返回 [-1, -1]。

我使用最死的二分查找，分别搜索起始和结束位置。这种思路也可以使用递归实现。

 1 vector<int> searchRange(vector<int>& nums, int target) {
 2     vector<int> result = {-1, -1};
 3     int low = 0, high = nums.size() - 1;
 4     while (low <= high) {
 5         // 二分查找使用 mid = (high + low) / 2 可能溢出
 6         int mid = low + ((high - low) >> 1);
 7         if (nums[mid] == target) {
 8             if (result[0] == -1) {
 9                 if (mid == 0 || nums[mid] != nums[mid - 1]) {
10                     result[0] = mid;
11                     low = 0, high = nums.size() - 1;
12                 }
13                 else
14                     high = mid - 1;
15             } else {
16                 if (mid == nums.size() - 1 || nums[mid] != nums[mid + 1]) {
17                     result[1] = mid;
18                     break;
19                 }
20                 else
21                     low = mid + 1;
22             }
23         }
24         else if (nums[mid] > target)
25             high = mid - 1;
26         else if (nums[mid] < target)
27             low = mid + 1;
28     }
29     return result;
30 }

C++ STL中自带一些使用二分查找实现的算法，

#include <algorithm>  
  pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val );  
  pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val, CompFn comp );

函数 equal_range 返回非递减序列 [first, last) 区间中等于 val 的元素区间，返回值是一对迭代器 i 和 j 。i 是 val 可插入的第一个位置（即lower_bound），j 是 val 可插入的最后一个位置（即upper_bound），equal_range 可以被认为是 lower_bound 和 upper_bound 的结合。

（lower_bound 在 [first, last) 区间进行二分查找，返回大于等于 val 的第一个元素位置。如果所有元素都小于 val，则返回 last 的位置。

upper_bound 在 [first, last) 区间进行二分查找，返回大于 val 的第一个元素位置）

因此以下代码可直接得出结果。

1 vector<int> searchRange(vector<int>& nums, int target) {
2     auto bounds = equal_range(nums.begin(), nums.end(), target);
3     if (bounds.first == bounds.second)
4         return {-1, -1};
5     return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
6 }

1 vector<int> searchRange(vector<int>& nums, int target) {
2     int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
3     if (lo == nums.size() || nums[lo] != target)
4         return {-1, -1};
5     int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
6     return {lo, hi};
7 }