Share my java AC solution. O(log n) without recursion.


  • 0
    S

    Suppose we have three pointers:start, mid and end. There are three case for the array between start and end:

    1. A[mid] < A[start]: Rotated, the maximum value is on the left of mid. If target < A[mid], then we search the left part; if target > A[mid], we then have two situations: (a) target <= A[end], we search the right part; (b) target > A[end], search the left part.

    2. A[mid] > A[end]: Rotated, the maximum value is on the right of mid. target > A[mid]: search the left part; target < A[mid] && < A[start]: search the right part; target < A[mid] && >= A[start]: search the left part.

    3. Otherwise: Not rotated. Just perform normal binary search.

    My code:

    public class Solution {
    public int search(int[] A, int target) {
        if (A.length==0) return -1;
    
        int start = 0, end = A.length-1;
        int mid = -1;
    
        while (start<=end){
            mid = (start+end)/2;
            if (A[mid]==target) return mid;
    
            if (A[mid]<A[start]){
                if (target<A[mid])
                    end = mid-1;
                else if (target<=A[end])
                    start = mid+1;
                else end = mid-1;
                continue;
            }
    
            if (A[mid]>A[end]){
                if (target>A[mid]) start = mid+1;
                else if (target>=A[start]) end = mid-1;
                else start = mid+1;
                continue;
            }
    
            if (target<A[mid]) end = mid-1;
            else start = mid+1;
        }
    
        return -1;
    }
    

    }


Log in to reply
 

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