Share my accepted iterative Java solution. Are there any better solutions?


  • 0
    S

    To solve the problem we have 4 cases to distinguish:

    1. A[mid] == target -> return mid
    2. A[start] < A[end] //i.e. both left and right halves are sorted - perform normal binary search
    3. right half is sorted - check if target value is between both ends of the right half; if it is - do binary search in the right half; else do binary search in the left half;
    4. left half is sorted - do the same as for the rigth half
     `public int search(int[] A, int target) {`
    
        int start = 0;
        int end = A.length-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(A[mid] == target)
                return mid;
            if(A[start] < A[end]){  //both halves are sorted
                if(A[mid] > target)
                    end = mid-1;
                else
                    start = mid+1;
            }
            else if(A[mid] < A[end]){   //right half is sorted
                if(A[mid] < target && target <= A[end])
                    start = mid+1;
                else
                    end = mid-1;
            }
            else{   //left half is sorted
                if(A[start] <= target && target < A[mid])
                    end = mid-1;
                else
                    start = mid+1;
            }
        }
        return -1;
    }
    

    Are there any better solutions?


Log in to reply
 

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