Java AC solution in O(logN)


  • 0
    S

    Modified version of binary search. When we find the target, we recursively use binary search to find the left range from left side and right range from the right side.

       public int[] bsearch(int[] A, int target, int start, int length) {
            int l = start;
            int r = start + length - 1;
            while (l<=r) {
                int mid = (l+r) /2;
                if (A[mid] == target) {
                    int s = l;
                    int e = r;
                    if (A[l] != target) {
                        final int[] ints = bsearch(A, target, l + 1, mid - l - 1);
                        s = ints[0] == -1 ? mid : ints[0];
                    }
                    if (A[r] != target) {
                        final int[] ints = bsearch(A, target, mid + 1, r - mid - 1);
                        e = ints[1] == -1 ? mid : ints[1];
                    }
                    return new int[]{s, e};
                }
                else if (A[mid] < target) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            return new int[]{-1, -1};
        }
    
        public int[] searchRange(int[] A, int target) {
            return bsearch(A, target, 0, A.length);
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.