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

Difficulty
Medium

Analysis

On sight of O(log n) time, we know it's going to be Binary Search.

Idea
Use binary search to find the left bound, then use binary search to find the right bound.

The trick here is how we use binary search to find the bound:
For a normal binary search, we return the index when nums[mid] == target, however, we don't return since we need to keep searching for bound index. So we set the condition to nums[mid] >= target for left bound, and nums[mid] <= target for right bound, outer loop condition is still low <= high.

We iterate over [0 ... n - 1] of the array to find the left bound, when nums[mid] >= target, we set high = mid - 1, otherwise, low = mid + 1, and keep looping until we found no value equals to target and get out of the loop, now low > high. If in the looping procedure we have ever found a value that equals to target and when we break out the loop, low < n, then we can make sure, the index low is the left bound. Based on this left bound, we iterate again the [low ... n - 1] of the array to find the right bound.

Solutions

1. Cpp solution 9ms

class Solution {
public:
    vector<int> searchRange(vector<int>& A, int target) {
        const int n = A.size();
        if(n == 0) {
            return {-1, -1};
        }

        vector<int> v;
        int low = 0;
        int high = n - 1;

        // Starting from position 0, binary search to find the left bound index of target value
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(A[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // if found lower bound
        if(low < n && A[low] == target) {
            v.push_back(low);
        } else { // if not found lower bound, no need to find higher bound
            return {-1, -1};
        }

        high = n - 1;
        // Starting from low position, conitnue to binary search for the right bound index of target value
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(A[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        v.push_back(high);
        return v;
    }
};

1. Go Solution 36ms

func searchRange(nums []int, target int) []int {

    n := len(nums)
    if n == 0 {
        return append([]int(nil), -1, -1)
    }

    low, high := 0, n - 1
    for low <= high {
        mid := low + (high - low) / 2
        if nums[mid] >= target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    res := make([]int, 2)
    if low < n && nums[low] == target {
        res[0] = low
    } else {
        return append([]int(nil), -1, -1)
    }

    high = n - 1
    for low <= high {
        mid := low + (high - low) / 2
        if nums[mid] <= target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    res[1] = high

    return res
}

Reference