LC 81, search in rotated array 2

The sorted array is rotated once, and we might have duplicate (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

We will still use binary search but this time the duplicate will give us an edge case:
[1,1,1,1,1,1,1,1,1,2,3,4] rotate -> [1,2,3,4,1,1,1,1,1,1,1]
low = 1, high = 1 and mid = 1 and we don’t know which part is sorted so we can either low ++ or high — to edge toward an interval where at least we know [low,mid] or [mid, high] is sorted.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(nums[mid] == target)
                return true;
            if(nums[low] < nums[mid]){//low-mid are sorted
                if(nums[low] <= target && target < nums[mid]){
                    high = mid - 1;
                }
                else{
                    low = mid + 1;
                }

            }
            else if(nums[mid] < nums[low]){  //mid-high are sorted
                if(nums[mid] < target && target <= nums[high]){
                    low = mid + 1;
                }
                else{
                    high = mid - 1;
                }
            }

            else{
                low ++;
            }

        }
        return false;
    }
};

bugs

else if condition

In else if, I first used

else if(nums[mid] < nums[high]

to decide if [mid, high] is sorted but it will fail at test case such as [3,1,1] t = 3.
low = 0 high = 2 mid = 1

we see that nums[low] !< nums[mid] so [low, mid] is not sorted so [mid, high] should be sorted, but our elseif statement is not true because nums[mid] == nums[high]. So we should just change elseif to the compliement of

if(nums[low] < nums[mid])

Which is

else if(nums[low] > nums[mid]

(Not exact complement since equality is already tested)

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax