Skip to content

Files

Latest commit

fa9d3c9 · Apr 21, 2015

History

History

SearchforaRange

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Apr 21, 2015
Apr 21, 2015
Apr 21, 2015

README.md

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