[LeetCode]Search for a Range

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

这道题在二分搜索的基础上做个修改：找出左边界与右边界。

找左边界：当A[mid]=target时，继续向左找，直到left>right

找右边界：当A[mid]=target时，继续向右找，直到left>right

如果target不存在的话，左边界的值会大于右边界的值。

下面给出一个找左边界的图例：

最后贴上代码：

class Solution {
public:
	vector<int> searchRange(int A[], int n, int target) {
		vector<int> vec(2, -1);
		if (n == 0){
			return vec;
		}
		int left = 0, right = n;
		int mid = 0;
		while (left < right){
			mid = (left + right) / 2;
			if (A[mid] >= target)
				right = mid;
			else
				left = mid + 1;
		}
		int l = left;
		left = 0;
		right = n;
		while (left < right){
			mid = (left + right) / 2;
			if (A[mid] <= target)
				left = mid + 1;
			else
				right = mid;
		}
		int r = right-1;
		if (l <= r){
			vec[0] = l;
			vec[1] = r;
		}
		return vec;
	}
};

[LeetCode]Search for a Range

原文：http://blog.csdn.net/kaitankedemao/article/details/43526199