Problem Description

P33

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

P81

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Solution

P33

The first thought is that if we know the pivot index, the problem can be solved by normal binary search. To search for pivot, we use another binary search to look for the index where it is larger than its right number.

The second idea is to realize that there is only one pivot position, which means the other part must be in order. We can check easily check if our target is within the range of this ordered part, then we know which part to do the search in the next step.

P81

The only difference here is we could have duplicate numbers, and this poses the issue when we do the binary search and find nums[mid]==nums[l], in this case, we do not know which part is in order. We could have for example: [4,5,1,4,4,4,4] or [4,4,4,4,5,1,3]. However, the key observation is that when nums[mid]==nums[l] and if the pivot is in the left part, then we must have nums[mid]==nums[l]==nums[r], or nums[l]==nums[r]. Note that we still cannot know in which part the pivot is when nums[mid]==nums[l]==nums[r]. What we could do is to separate to have two cases nums[l]==nums[r] and nums[l]!=nums[r]. While in the latter case nums[l]!=nums[r], and if nums[mid]==nums[l], then we immediately know the pivot is in the right part. In the first case nums[l]==nums[r], we simply shrink the range by incrementing l and decrementing r if target!=nums[l].

Another treatment when nums[mid]==nums[l] is that we only incrementing l and do not update mid in this step.

Java Code

P33

Find the pivot

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length, pivot = 0;
        if(len==1) return nums[0]==target ? 0 : -1;
        int l = 0, r = len-1;
        int mid;
        if(nums[len-1] < nums[0]){    
            while( l < r){
                mid = (l+r) / 2;
                if( nums[l] < nums[mid] ) l = mid;
                else r = mid;
            }
            pivot = len-l-1;
        }
        l = 0;
        r = len-1;
        while( l <= r ){
            mid = ( (l+r)/2 + len - pivot ) % len;
            if( nums[mid] < target) l = (l+r)/2+1;
            else if( nums[mid] > target) r = (l+r)/2-1;
            else return mid;
        }
        return -1;
    }
}

One binary search

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int l = 0, r = len-1, mid;
        while( l<= r){
            mid = (l+r)/2;
            if(nums[mid] == target) return mid;
            if(nums[l] == target) return l;
            if(nums[r] == target) return r;
            if( nums[l] < nums[mid]){
                if( target>nums[l] && target<nums[mid] ) r = mid-1;
                else l = mid+1;
            }else{
                if( target>nums[mid] && target<nums[r] ) l = mid+1;
                else r = mid-1;
            }
        }
        return -1;
    }
}

P81

Check nums[l] and nums[r]

class Solution {
    public boolean search(int[] nums, int target) {
        int len = nums.length, l=0, r=len-1, mid;
        while( l <= r){
            mid = (l+r)/2;
            if( nums[mid] == target) return true;
            if( nums[l] == nums[r] ) {
                if( nums[l] == target) return true;
                l++; r--;
                continue;
            }
            if( nums[l] <= nums[mid] ) {// the left part is in order
                if( target>=nums[l] && target<=nums[mid] ) r = mid-1;
                else l = mid+1;
            }else{ // the right part is in order
                if( target>=nums[mid] && target<=nums[r] ) l = mid+1;
                else r = mid-1;
            }
        }
        return false;
    }
}

Incrementing l by 1 when nums[l]==nums[mid]

class Solution {
    public boolean search(int[] nums, int target) {
        int len = nums.length, l=0, r=len-1, mid;
        while( l <= r){
            mid = (l+r)/2;
            if( nums[mid] == target) return true;
            if( nums[l] < nums[mid] ) {// the left part is in order
                if( target>=nums[l] && target<=nums[mid] ) r = mid-1;
                else l = mid+1;
            }else if( nums[l] > nums[mid] ){ // the right part is in order
                if( target>=nums[mid] && target<=nums[r] ) l = mid+1;
                else r = mid-1;
            }else l++;
        }
        return false;
    }
}