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.

Analysis

• high = nums.length - 1: 这里high用len-1而不是len是因为下面需要比较target和nums[high]的大小,nums[high]要有意义
• while 条件选择：
  • 最后跳出的情况有两种：low+1==high，或者low==high。这两种情况就可以跳出并且能够保证找到答案了。所以选择low+1<high，两种情况均跳出循环。
  • low <= high：不可取。如果low==high，则死循环。比如{1},0,low==high==0。
  • low < high: 不可取。low+1==high时,mid==low,可能死循环。比如{1,3},2, low=0, high=1, mid=0，low和high不更新，死循环。

Code

public class Solution {
    public int search(int[] nums, int target) {
        if (nums==null || nums.length==0) {return -1;}

       int low = 0;
       int high = nums.length-1;//这里high用len-1而不是len是因为下面需要比较target和nums[high]的大小,nums[high]要有意义

       while (low +1 < high){ 

           int mid = low + (high-low)/2;

           if (target == nums[mid]) {return mid;}

           if (nums[mid]>nums[low]){//1st half is sorted
               if (target > nums[mid]) {low = mid;}
               else {
                   if (target == nums[low]) {return low;}
                   else if (target > nums[low]) {high = mid;}
                   else {low = mid;}
               }
           }
           else {//2nd half is sorted
               if (target < nums[mid]) {high = mid;}
               else {
                   if (target == nums[high]) {return high;}
                   else if (target >nums[high]) {high = mid;}
                   else {low = mid;}
               }
           }
       }

       if (nums[low]==target) {return low;}
       if (nums[high]==target) {return high;}

       return -1;
    }
}

Note

• 为什么变边界时low=mid, high=mid??

Reference

Yuanbin