剑指 Offer 53

思路

排序数组中的搜索问题，首先想到二分法解决。

方法一：二分法之一 (类似暴力)

(1) 用二分法找到其中一个target所在的位置

(2) 之后在此位置前后顺序查找依次计数target的出现次数。(有点暴力，在方法二对此有改进)

复杂度分析

时间复杂度：最坏情况下O(n)

空间复杂度：O(1)

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         if(nums.empty()) {
 5             return 0;
 6         }
 7 
 8         /*二分查找*/
 9         int left = 0, right = nums.size()-1;
10         int mid;
11 
12         /*先找到其中一个target所在的位置mid*/
13         while(left <= right) {
14             mid = (left + right) / 2;
15             if(nums[mid] < target) {
16                 left = mid + 1;
17             } else if(nums[mid] > target) {
18                 right = mid - 1;
19             } else {
20                 break;
21             }
22         }
23 
24         /*之后在mid前后顺序查找依次计数target的出现次数*/
25         if(nums[mid] == target) {
26             int res = 0;
27             for(int i = mid; i >= 0; --i) {
28                 if(nums[i] == target)
29                     ++res;
30             }
31 
32             for(int i = mid+1; i < nums.size(); ++i) {
33                 if(nums[i] == target)
34                     ++res;
35             }
36 
37             return res;
38 
39         } else {
40             return 0;
41         }
42     }
43 };

方法二：二分法

上述方法可以改进，

排序数组 nums 中的所有数字 target 形成一个窗口，记窗口的左 / 右边界索引分别为 targetLeft和 targetRight 。即：targetLeft表示第一个target的位置，targetRight 表示最后一个target的位置。

本题要求统计数字 target 的出现次数，可转化为：使用两次二分法分别找到左边界 targetLeft和右边界 targetRight ，易得数字 target的数量为 targetRight - targetLeft + 1 。

复杂度分析

时间复杂度：O(logn)

空间复杂度：O(1)

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         if(nums.empty()) {
 5             return 0;
 6         }
 7 
 8         int left, right, mid;
 9 
10         /*第一次二分：搜索右边界targetRight*/
11         left = 0, right = nums.size()-1;
12         while(left <= right) {
13             mid = (left + right) / 2;
14             if(nums[mid] <= target) {
15                 left = mid + 1;
16             } else {
17                 right = mid - 1;
18             } 
19         }
20 
21         //targetRight就是最右侧那个target的位置
22         int targetRight = left-1;
23 
24         //找不到target的情况
25         if( targetRight < 0 || (targetRight >= 0 && nums[targetRight] != target) )
26             return 0;
27 
28         /*第二次二分：搜索左边界targetLeft*/
29         left = 0, right = nums.size()-1;
30         while(left <= right) {
31             mid = (left + right) / 2;
32             if(nums[mid] < target) {    //注意这里和第一次二分的区别
33                 left = mid + 1;
34             } else {
35                 right = mid - 1;
36             } 
37         }
38 
39         //targetLeft就是最左侧target的位置
40         int targetLeft = right + 1;
41 
42         return targetRight - targetLeft + 1;
43 
44     }
45 };

相似题目：

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

剑指 Offer 53 - II. 0～n-1中缺失的数字