Neat JAVA solution using binary search


  • 24
    M
        public boolean search(int[] nums, int target) {
            int start = 0, end = nums.length - 1, mid = -1;
            while(start <= end) {
                mid = (start + end) / 2;
                if (nums[mid] == target) {
                    return true;
                }
                //If we know for sure right side is sorted or left side is unsorted
                if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
                    if (target > nums[mid] && target <= nums[end]) {
                        start = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                //If we know for sure left side is sorted or right side is unsorted
                } else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
                    if (target < nums[mid] && target >= nums[start]) {
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                    }
                //If we get here, that means nums[start] == nums[mid] == nums[end], then shifting out
                //any of the two sides won't change the result but can help remove duplicate from
                //consideration, here we just use end-- but left++ works too
                } else {
                    end--;
                }
            }
            
            return false;
        }
    

    In case anyone wonders, yes I agree that we don't need to check two parts. It's just that Doing that can slightly boost the performance, no asymptotic difference though.


  • 24
    H

    No need to check two parts. We must have one part sorted while the other part rotated.

    public boolean search(int[] nums, int target) {
        int start  = 0, end = nums.length - 1;
        
        //check each num so we will check start == end
        //We always get a sorted part and a half part
        //we can check sorted part to decide where to go next
        while(start <= end){
            int mid = start + (end - start)/2;
            if(nums[mid] == target) return true;
            
            //if left part is sorted
            if(nums[start] < nums[mid]){
                if(target < nums[start] || target > nums[mid]){
                    //target is in rotated part
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }else if(nums[start] > nums[mid]){
                //right part is rotated
                
                //target is in rotated part
                if(target < nums[mid] || target > nums[end]){
                    end = mid -1;
                }else{
                    start = mid + 1;
                }
            }else{
                //duplicates, we know nums[mid] != target, so nums[start] != target
                //based on current information, we can only move left pointer to skip one cell
                //thus in the worest case, we would have target: 2, and array like 11111111, then
                //the running time would be O(n)
                start ++;
            }
        }
        
        return false;
    }

  • 0
    M

    You are right, I was just checking two parts so that less cases falls into the "else" part. Doing that can slightly boost the performance, no asymptotic difference though.


  • 0
    F

    Using the following test case:
    int[] nums = { 11, 10, 9, 8, 7, 6, 5, 4, 3, 0, 1, 2 };
    int target =4;

    The output should be true, because 4 is in the array, but actually the out put is "false".


  • 0
    P

    @fei3854 Your test case is not an array sorted in ascending order which then is rotated at some pivot


  • 0
    X

    I‘m confused a little bit, can someone explain that the mid which is computed by the start and the end is in ascending array or in rotated array?


Log in to reply
 

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