Search for a Range

Description

Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Challenge
O(log n) time.

Link

Lintcode_ladder

Method

1. Double Binary search
2. x

Example

1. 1

class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
public:
    vector<int> searchRange(vector<int> &nums, int target) {
        // write your code here
        if (nums.empty()) {
            return {-1, -1};
        }
        vector<int> result = {-1, -1};
        // for the left bound
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start+(end-start)/2;
            if (target <= nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target == nums[start]) {
            result[0] = start;
        } else if (target == nums[end]) {
            result[0] = end;
        }
        // for the right bound
        // keep start
        // start = start;
        end = nums.size()-1;
        while (start+1 < end) {
            int mid = start+(end-start)/2;
            if (target < nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target == nums[end]) {
            result[1] = end;
        } else if (target == nums[start]) {
            result[1] = start;
        }
        return result;
    }
};

Similar problems

x

Tags

x