Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
思路：二分。。。
我好像根本不会二分啊？？？
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 10时49分02秒
4File Name :34.cpp
5************************************************ */
6class Solution {
7
8public:
9
10 int n;
11 vector<int>res;
12 int bin(int l,int r,vector<int>& nums,int tar) //
13 {
14 while (l<=r)
15 {
16 int mid = (l+r)>>1;
17 if (nums[mid]>=tar) r = mid - 1;
18 else l = mid + 1;
19 }
20 return nums[r+1]==tar?r+1:-1;//找到第一个等于tar的下标
21 }
22 int bin2(int l,int r,vector<int>& nums,int tar)
23 {
24 while (l<=r)
25 {
26 int mid = (l+r)>>1;
27 if (nums[mid]>tar) r = mid-1;
28 else l = mid + 1;
29 }
30 return nums[l-1]==tar?l-1:-1; //找到最后一个等于tar的下标
31 }
32 vector<int> searchRange(vector<int>& nums, int target) {
33 n = nums.size();
34 if (n==0) return vector<int>(2,-1);
35 int L = bin(0,n-1,nums,target);
36 int R = bin2(0,n-1,nums,target);
37 if (L>=n) L = -1; //对于只有一个数的情况，需要维护一下。
38 if (R>=n) R = -1;
39 res.push_back(L);
40 res.push_back(R);
41 return res;
42 }
43
44};