My recursive binary search solution in Java


  • 0
    G

    The solution is quite ugly...

    public class Solution {
        private int left = -1;;
        private int right = -1;
        
        public int[] searchRange(int[] A, int target) {
            int n = A.length;
            binaryRangeSearch(A, target, 0, n-1);
            int[] result = new int[2];
            result[0] = left;
            result[1] = right;
            return result;
        }
        
        private void binaryRangeSearch(int[] A, int target, int lo, int hi) {
            if (lo > hi)    return;
            
            int mid = lo + (hi - lo) / 2;
            if (target == A[mid]) {
                if (left == -1 || right == -1) {
                    left = mid;
                    right = mid;
                } else {
                    if (mid < left) left = mid;
                    if (mid > right) right = mid;
                }
                if (mid > lo && mid <= left && A[mid-1] == A[mid])
                    binaryRangeSearch(A, target, lo, mid-1);
                if (mid < hi && mid >= right && A[mid] == A[mid+1])
                    binaryRangeSearch(A, target, mid+1, hi);
                
            } else if (target > A[mid]) 
                binaryRangeSearch(A, target, mid+1, hi);
            else 
                binaryRangeSearch(A, target, lo, mid-1);
        }
    }

Log in to reply
 

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