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

• Binary search for the number, then expand our left and right from that index until you reach a different 'target' number. This will give us the range of numbers, but it doesn't run in O(logn). Consider the case when all the numbers in the array are the target number. Then binary search would return the middle index, and then expanding out left and right would run in O(n).

int binary_search(vector<int> &nums, int low, int high, int key) {
    if (high < low) return -1;
    int median = low + ((high - low) / 2);
    if (nums.at(median) == key) {
        return median;
    }
    else if (nums.at(median) < key) {
        // search right
        return binary_search(nums, median + 1, high, key);
    }
    else {
        // search left
        return binary_search(nums, low, median - 1, key);
    }
}


vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> range(2);
    // find the number
    int index = binary_search(nums, 0, nums.size() - 1, target);
    if (index == -1) {
        return range = { -1, -1 };
    }
    else {
        // expand right
        int i;
        for (i = index; i < nums.size(); i++) {
            if (nums.at(i) != target) {
                break;
            }
        }

        // expand left
        int j;
        for (j = index; j >= 0; j--) {
            if (nums.at(j) != target) {
                break;
            }
        }
        return range = { j + 1, i - 1 };
    }
}

Improved O(logN) version

• Simply replace with this function

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> range(2);

    // find the number
    int index = binary_search(nums, 0, nums.size() - 1, target);

    if (index == -1) {
        return range = { -1, -1 };
    }

    // expand left
    int prev_left = index;
    int left = index;
    while (left != -1) {
        prev_left = left;
        left = binary_search(nums, 0, --left, target);
    }
    left = prev_left;

    // expand right
    int prev_right = index;
    int right = index;
    while (right != -1) {
        prev_right = right;
        right = binary_search(nums, ++right, nums.size() - 1, target);
    }
    right = prev_right;

    return range = { left, right };
}

• Rather than just expanding left and right linearly, we first find the target with binary search, and then we binary search out right and left directions. The first occurance that the number is not found, means that the index returned by the previous iteration was the edge case, and hence in part of the maximum range.