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

這里面沒(méi)有重復(fù)的元素
先找到最小的元素，這是數(shù)組真正的頭，這個(gè)通過(guò)二分法可以找到著觉。
然后再通過(guò)二分法找要找的數(shù)佩番，這時(shí)找中點(diǎn)時(shí)可以利用剛才的結(jié)果鳞尔，以找到真正的中間點(diǎn)陵叽。

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;
        //如果中點(diǎn)就是我們要找的
        if(nums[mid] == target) 
            return mid;
        //如果左邊的小于等于中間的潘靖，那意味著中點(diǎn)以左是有序區(qū)
        else if(nums[left] <= nums[mid])
        {
            //看看target在不在左邊有序區(qū)
            if( (nums[left]<=target) && (nums[mid] > target) ) 
                right = mid-1;
            else 
                left = mid + 1; 
        }
        //如果左邊的大于中間的芒划，那意味著中點(diǎn)以右是有序區(qū)
        else
        {
            //看看target在不在右邊有序區(qū)
            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.
如果數(shù)組里有重復(fù)冬竟，那上面找最小值的辦法就不管用了，改進(jìn)一下第二個(gè)方法民逼，如果中間值與兩邊值相等泵殴，兩邊的指針都向中間挪。

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;
};