SearchforaRange

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].

Solution

二分搜索

首先找到target索引， 若不存在返回[-1, -1], 否则找到左边界和右边界

找左边界，设二分搜索的结果为left, mid, 则设left = left, right = mid:

• 若left == right, 返回right
• 若a[left] == target，left就是左边界.比如[7,8,8,8], left = 1, target = 8
• 若a[right - 1] != target, right就是左边界.比如[1,6,8,9], right = 2, target = 8`
• 设mid = left + ((right - left) >> 1), 若a[mid] == target, 则right = mid, 否则必然有 a[mid] < target, 则left = mid + 1
• 返回最开始。

找右边界类似

class Solution {
public:
    vector<int> searchRange(int a[], int n, int target) {
	    vector<int> result(2, -1);
	    if (a == nullptr || n == 0)
		    return result;
	    int left = 0, right = n - 1;
	    bool found = false;
	    int mid = 0;
	    while (left <= right) {
		    mid = left + ((right - left) >> 1);
		    if (a[mid] == target) {
			    found = true;
			    break;
		    } else if (a[mid] < target) {
			    left = mid + 1;
		    } else {
			    right = mid - 1;
		    }
	    }
	    if (found) {
		    result[0] = leftSearch(a, left, mid, target);
		    result [1] = rightSearch(a, mid, right, target);
	    }
	    return result;
    }
private:
    int leftSearch(int a[], int start, int end, int target) {
	    int left = start, right = end;
	    while (left < right && a[right - 1] == target) {
		    if (a[left] == target)
			    return left;
		    int mid = left + ((right - left) >> 1);
		    if (a[mid] == target)
			    right = mid;
		    else
			    left = mid + 1;
	    }
	    return right;
    }
    int rightSearch(int a[], int start, int end, int target) {
	    int left = start, right = end;
	    while (left < right && a[left + 1] == target) {
		    if (a[right] == target)
			    return right;
		    int mid = left + ((right - left) >> 1);
		    if (a[mid] == target) {
			    left = mid;
		    }
		    else {
			    right = mid - 1;
		    }
	    }
	    return left;
    }
};