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

Example:

Given [5, 7, 7, 8, 8, 10]

and target value 8,

return [3, 4].

思路:

这题和Count Element Occurrence是一样的。

Solution:

Time: O(logn)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST
    public ArrayList<Integer> searchRange(final List<Integer> a, int b) {
        // [5, 7, 7, 8, 8, 10]
        ArrayList<Integer> result = new ArrayList<>();
        result.add(-1);
        result.add(-1);
        int left = 0;
        int l = 0;
        int right = a.size() - 1;
                     r  l
        // [5, 7, 7, 8, 8, 10] when binary search finishes
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a.get(mid) >= b) {
                right = mid - 1;
            } else {
                left = mid + 1;
                l = left;
            }
        }
        left = 0;
        right = a.size() - 1;
                             r    l
        // [5, 7, 7, 8, 8, 10]  when binary search finishes
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a.get(mid) <= b) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (right - l + 1 > 0) {
            result.set(0, l);
            result.set(1, right);
        }
        return result;
    }
}