034在排序数组中查找元素的第一个和最后一个

 1 #include "000库函数.h"
 2 
 3 //使用二分法查找到目标值的位置，然后分两边再查找出起始位置和终止位置
 4 //16ms  不是严格意义上的logn的复杂度
 5 class Solution {
 6 public:
 7     vector<int> searchRange(vector<int>& nums, int target) {
 8         vector<int>v = { -1,-1 };
 9         int i = 0, j = nums.size() - 1;
10         int m = -1;
11         while (i <= j) {
12             int t = (i + j) / 2;
13             if (nums[t] == target) {
14                 m = t;
15                 break;
16             }
17             if (nums[t] > target)    j = t - 1;
18             else i = t + 1;
19         }
20         if (m == -1) return v;    
21         int t = m;
22         while (t >= 0 && nums[t] == target) --t; 
23         v[0] = (t + 1);
24         t = m;
25         while (t < nums.size() && nums[t] == target) ++t;
26         v[1] = (t - 1);
27         return v;
28     }
29 };
30 
31 //复杂度满足logn   
32 class Solution {
33 public:
34     vector<int> searchRange(vector<int>& nums, int target) {        
35         vector<int> res(2, -1);
36         if (nums.size() == 0)return res;
37         int left = 0, right = nums.size() - 1;
38         while (left < right) {
39             int mid = left + (right - left) / 2;
40             if (nums[mid] < target) left = mid + 1;//使用这种判断，会找到最左边的目标值
41             else right = mid;
42         }
43         if (nums[right] != target) return res;
44 
45         res[0] = right;
46         right = nums.size();
47         while (left < right) {
48             int mid = left + (right - left) / 2;
49             if (nums[mid] <= target) left = mid + 1;//使用这种判断，会找到最右边的目标值
50             else right = mid;
51         }
52         res[1] = left - 1;
53         return res;
54     }
55 };
56 void T034() {
57     Solution s;
58     vector<int >n;
59     n = { 8 };
60     n = s.searchRange(n, 8);
61     cout << n[0] << "  " << n[1] << endl;
62     n = { 5,7,7,8,8,10 };
63     n = s.searchRange(n, 9);
64     cout << n[0] << "  " << n[1] << endl;
65     n = { 5,7,7,8,8,8,10 };
66     n = s.searchRange(n, 8);
67     cout << n[0] << "  " << n[1] << endl;
68     n = { 1,1,1,1,1,1};
69     n = s.searchRange(n,1);
70     cout << n[0] << "  " << n[1] << endl;
71 
72 }