Search for a Range

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

Naive Way:因为是排好序的，所以只需要通过二分搜索（假如要搜索8) [...7,8...] 和[...8,9...]这样的两个位置。

算法复杂度是O(logn)

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] range = new int[2];
        if(A.length==0){return range;}
        range[0] = A[0]==target?0:binarySearch(A, target, true);
        range[1] = A[A.length-1]==target?A.length-1:binarySearch(A, target, false);
        return range;
    }
    
    private int binarySearch(int[] A, int target, boolean downOrUp){
        int begin = 0, end = A.length-1;
        int middle = 0;
        while(begin < end){
            middle = (begin+end)/2;
            // find lower bound
            if(A[middle] < target && A[middle+1] == target && downOrUp)
                return middle+1;
            if(A[middle+1] < target && downOrUp)
                begin = middle+1;
            if(A[middle+1] >= target && downOrUp)
                end = middle;
            // find upper bound
            if(A[middle] == target && A[middle+1] > target && !downOrUp)
                return middle;
            if(A[middle] <= target && !downOrUp)
                begin = middle+1;
            if(A[middle] > target && !downOrUp)
                end = middle;
        }
        return -1;
    }
}