leetcode 34. Search for a Range (二分,找到一段值为tar的区间)

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 {
public:
 1    int n;
 2    vector<int>res;
 3    int bin(int l,int r,vector<int>& nums,int tar) //
 4    {
 5	while (l<=r)
 6	{
 7	    int mid = (l+r)>>1;
 8	    if (nums[mid]>=tar) r = mid - 1;
 9	    else l = mid + 1;
10	}
11	return nums[r+1]==tar?r+1:-1;//找到第一个等于tar的下标
12    }
13    int bin2(int l,int r,vector<int>& nums,int tar)
14    {
15	while (l<=r)
16	{
17	    int mid = (l+r)>>1;
18	    if (nums[mid]>tar) r = mid-1;
19	    else l = mid + 1;
20	}
21	return nums[l-1]==tar?l-1:-1; //找到最后一个等于tar的下标
22    }
23    vector<int> searchRange(vector<int>& nums, int target) {
24        n = nums.size();
25	if (n==0) return vector<int>(2,-1);
26	int L = bin(0,n-1,nums,target);
27	int R = bin2(0,n-1,nums,target);
28	if (L>=n) L = -1; //对于只有一个数的情况,需要维护一下。
29	if (R>=n) R = -1;
30	res.push_back(L);
31	res.push_back(R);
32	return res;
33    }
};