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;
	}