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]

.

思路：这道题很容易想到的思路是利用二分查找找到target，然后以找到的target为中心向前向后遍历，这种方法由于还需要有一个遍历的过程，所以在最坏情况下的时间复杂度是O(n)。

vector<int> searchRange(int A[], int n, int target) {
        int low = 0;
		int high = n - 1;
		vector<int>v;
		int index = binarySearch(A,low,high,target);
		//printf("%d\n",index);
		if(index == -1){
			v.push_back(-1);
			v.push_back(-1);
			return v;
		}
		low = index;
		high = index;
		while( low >= 0 && A[low] == target )
			low--;
		while(high < n && A[high] == target)
			high++;
		v.push_back(++low);
		v.push_back(--high);
		return v;
		
    }
	int binarySearch(int A[],int low,int high,int target){
		if(low <= high){
			int mid= (low + high)/2;
			if(A[mid] == target)
				return mid;
			if(A[mid] > target)
				return binarySearch(A,low,mid - 1,target);
			else
				return binarySearch(A,mid + 1,high,target);
		}
		else
			return -1;
		
	}
           

另一种思路是直接利用二分查找寻找target的下限和上限，寻找下限的原则是不错过第一个相等的元素，寻找上限的原则是不错过最后一个相等的元素，这里边有一个问题是mid在取值时更加靠近low，所以寻找上限与寻找下限时指针的移动稍有不同，这点儿需要注意。

vector<int> searchRange(int A[], int n, int target) {
	    int low = 0;
		int high = n - 1;
		//找下限
		vector<int>v(2,-1);
		while(low < high){
		    int mid = (low + high) / 2;
			if(A[mid] < target)  //原则是不能错过最前一个相等元素
				low = mid + 1;
			else
				high = mid;				
		}
		if(A[low] != target)
			return v;
		v[0] = low;
		//找上限
		high = n - 1;      
		while(low < high){  
			int mid = (low + high) / 2;
			if(A[mid] > target)    //原则是不能错过最后一个相等元素
				high = mid - 1;
			else
				low = mid + 1;//因为low之后的元素不比target小，所以此处是A[low] = target,但仍需向前移动，否则容易陷入死循环。
		}
		if(A[high] == target)
		     v[1] = high;
		else
			v[1] = high - 1;
		return v;
	}