[Solution] O(logn) binary search solution with explanation (Java)


  • 4
    S
    public class Solution {
        public int searchHelper(int[] A, int target, int start, int end){
            if(start>end){
                return -1;
            }
            int mid = (start+end)/2;
            if(A[mid] == target){
                return mid;
            }
            
            //Case 1: Left half is sorted
            if(A[mid] >= A[start]){
                if(target >= A[start] && target <= A[mid]){
                    return searchHelper(A,target,start,mid-1);    
                }
                else{
                    return searchHelper(A,target,mid+1,end);
                }
            }
            //Case 2: Right half is sorted
            if(A[end]>=A[mid]){
                if(target>=A[mid] && target<=A[end]){
                    return searchHelper(A,target,mid+1,end);
                }
                else{
                    return searchHelper(A,target,start,mid-1);
                }
            }
            return -1;
        }
        
        public int search(int[] A, int target) {
            return searchHelper(A,target,0,A.length-1);
        }
    }
    

    Given the assumption of unique elements, there are 2 possibilities:

    1. Left half is sorted i.e. pivot is in right half
    2. Right half is sorted i.e. pivot is in left half

    If target value is within the range of sorted half, binary search continues there.

    Otherwise, binary search continues in the half with the pivot.


  • 0
    A

    Same idea without recursion:

    public int search(int[] A, int target) {
            int low = 0;
            int high = A.length-1;
            while (low < high) {
                int mid = (low + high + 1)/2;
                if (A[mid] == target) return mid;
                if (A[mid] > A[low]) {
                    if (target < A[low] || target > A[mid]) {
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                } else {
                   if (target < A[mid] || target > A[high]) {
                       high = mid - 1;
                   } else {
                       low = mid+1;
                   }
                }
            }
            return low < A.length && A[low] == target ? low : -1;
        }

  • 0
    M

    good idea!! and explanation is clear..
    i think the last line 'return -1' in the method searchHelper is needless,because the first two line is the base case of recursion.


  • 0
    L

    you need this last line "return -1", otherwise it will lead to compile error since there are not all returns for all complete if/else statements


Log in to reply
 

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