LeetCode Search for a Range搜索特定数值的范围 三种方法求解

Given a sorted array of integers, 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,-1]。注意时间效率是O(longN)。这就肯定要用到二分法的思想了。

主要难度是处理好下标的走势。

有三种方法可以求解：

1 调用STL，不过注意处理调用后的返回值。

vector
  
    searchRange(int A[], int n, int target) 
	{
		auto itup = upper_bound(A, A+n, target);
		auto itlow = lower_bound(A, A+n, target);
		vector
   
     res; if (*itlow == target) res.push_back(itlow-A); else res.push_back(-1); if (*(itup-1) == target) res.push_back(itup-A-1); else res.push_back(-1); return res; }
   
  

2 模仿STL写这个程序，注意处理结果

vector
  
    searchRange2(int A[], int n, int target) 
	{
		int step = 0;
		int it = 0;
		int first = 0;
		vector
   
     res; for (int count = n; count>0;) { it = first; step=count/2; it += step; if (A[it]
    
     0;) { it = first; step=count/2; it += step; if (!(A[it]>target)) { first=++it; count-=step+1; } else count=step; } res.push_back(first-1); return res; }
    
   
  

3 思路：

一） 二分法查找到target

二）两边扩张找相等的值

	vector
  
    searchRange3(int A[], int n, int target) 
	{
		int mid = biSearch(A, 0, n-1, target);
		vector
   
     res(2,-1); if (mid == -1) return res; int t = mid; for (t = mid; t > 0 && A[t] == A[t-1]; t--); res[0] = t; for (t = mid; t < n-1 && A[t] == A[t+1]; t++); res[1] = t; return res; } int biSearch(int A[], int low, int up, int tar) { if (low>up) return -1; int mid = low + ((up-low)>>1); if (A[mid] < tar) return biSearch(A, mid+1, up, tar); if (A[mid] > tar) return biSearch(A, low, mid-1, tar); return mid; }