Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

方法1

这里面没有重复的元素
先找到最小的元素，这是数组真正的头，这个通过二分法可以找到。
然后再通过二分法找要找的数，这时找中点时可以利用刚才的结果，以找到真正的中间点。

var search = function(nums, target) {
    var left = 0;
    var right = nums.length - 1;
    while (left<right) {
        let mid = left + parseInt((right - left) / 2);
        if (nums[mid]>=nums[left]&&nums[mid]>=nums[right]) 
            left = mid + 1;
        else if (nums[mid]<=nums[left]&&nums[mid]<=nums[right]) 
            right = mid;
        else if (nums[mid]>=nums[left]&&nums[mid]<=nums[right]) 
            break;
    }
    var rot = left;
    left=0;
    right=nums.length-1;
    while(left<=right){
        let mid = left + parseInt((right - left) / 2);
        var realmid=(mid+rot)%nums.length;
        if(nums[realmid]==target)return realmid;
        if(nums[realmid]<target)left=mid+1;
        else right=mid-1;
    }
    return -1;
};

方法2

我们就正常的按照二分法的步骤走。

var search = function(nums, target) {
    var left = 0;
    var right = nums.length - 1;
    var mid;
    while(left<=right)
    {
        mid = (left + right) >> 1;
        //如果中点就是我们要找的
        if(nums[mid] == target) 
            return mid;
        //如果左边的小于等于中间的，那意味着中点以左是有序区
        else if(nums[left] <= nums[mid])
        {
            //看看target在不在左边有序区
            if( (nums[left]<=target) && (nums[mid] > target) ) 
                right = mid-1;
            else 
                left = mid + 1; 
        }
        //如果左边的大于中间的，那意味着中点以右是有序区
        else
        {
            //看看target在不在右边有序区
            if((nums[mid] < target) &&  (nums[right] >= target) ) 
                left = mid+1;
            else 
                right = mid-1;
        }
    }
    return -1;
};

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
如果数组里有重复，那上面找最小值的办法就不管用了，改进一下第二个方法，如果中间值与两边值相等，两边的指针都向中间挪。

var search = function(nums, target) {
    var left = 0;
    var right = nums.length - 1;
    var mid;
    while(left<=right)
    {
        mid = (left + right) >> 1;
        if(nums[mid] == target) 
            return true;
        //如果中间和两边相等，左右各往中间挪
        if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {
            ++left; 
            --right;
        }
        else if(nums[left] <= nums[mid])
        {
            if( (nums[left]<=target) && (nums[mid] > target) ) 
                right = mid-1;
            else 
                left = mid + 1; 
        }
        else
        {
            if((nums[mid] < target) &&  (nums[right] >= target) ) 
                left = mid+1;
            else 
                right = mid-1;
        }
    }
    return false;
};