Question

link

Stats

Frequency	3
Difficulty	4
Adjusted Difficulty	4
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

The key to solve this problem is binary search. Previously my solution is to find the element first, then check left bound and right bound respectively. In worst case, this will take O(n) time. This method, though, will pass OJ, but is not an optimized solution.

First solution is from this blog. Using binary search to search twice - once for left bound, and once for right bound. Code is below.

Second solution is from this blog. This idea is still using binary search, also search twice, but a more tricky manner. Instead of searching the number, it searches (number - 0.5) and (number + 0.5).

My code

Solution 1

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] ans = new int[] {-1, -1};
        if (A == null || A.length == 0) {
            return ans;
        }
        int len = A.length;
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (A[left] == target) {
            ans[0] = left;
        } else {
            return ans;
        }
        left = 0;
        right = len - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (A[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        ans[1] = right;
        return ans;
    }
}

Solution 2

public int[] searchRange(int[] A, int target) {
    if (A == null) return null;
    int[] result = { -1, -1 };
    int low = binarySearch(A, target - 0.5);
    // Be care for there , low>=A.length must be checked
    if (low >= A.length || A[low] != target) return result;
    result[0] = low;
    result[1] = binarySearch(A, target + 0.5) - 1;
    return result;
}

public int binarySearch(int[] A, double t) {
    int low = 0, high = A.length - 1;
    while (low <= high) {
        int m = (low + high) / 2;
        if (A[m] < t) low = m + 1;
        if (A[m] > t) high = m - 1;
    }
    return low;
}