leetcode

题意：

将一个升序数组，从中切断，将切断点后面的序列拼接到前面。注：切断点也可能在最后一个数字之后，即数组保持升序不变。

注意：数组中可能有重复数字。

分析：

这个数组长什么样呢？

            *  *

       *

   *

*

                                     *

                         *    *

                    *

可能是长这样的，甚至长这样。

* * * * * * * *

我们怎么能确定mid落在哪个区间呢？通过和nums[  low ]    或者nums[ high ]比较是可以得到的。但是原来的大于等于或者小于等于就不一定得到了。必须要大于或者小于才能充分证明可以得到。

至于当等于的时候， 比如 nums[ low ] == nums[ mid ]

说明可能是这样：

    *

*       *     *      *

low  mid

我们可以low++,来打破这种相等，从而可以判断区间，当然如果一直无法打破，那么就是全等的极端情况，只能依赖low++的顺序搜索, 最坏情况时间复杂度logn变n了。

public class Solution { public boolean search(int[] nums, int target) { int low = 0; int high = nums.length-1; while(low<=high){ int mid = low + (high - low)/2; if(nums[mid] == target) return true; if(nums[mid] > nums[low]){ //则一定在左上区间 if(target>=nums[low] && target<nums[mid]){ high = mid - 1; }else{ low = mid + 1; } }else if(nums[mid] < nums[low]){ //则一定在右下区间 if(target>nums[mid] && target<=nums[high]){ low = mid + 1; }else{ high = mid - 1; } }else{ low++; } } return false; } }

public class Solution { public boolean search(int[] nums, int target) { int start = 0, end = nums.length - 1; while(start <= end){ int mid = start + (end - start)/2; if(nums[mid] == target) return true; if(nums[start] < nums[mid]){ if(target < nums[start] || target > nums[mid]){ start = mid + 1; }else{ end = mid - 1; } }else if(nums[start] > nums[mid]){ if(target < nums[mid] || target > nums[end]){ end = mid -1; }else{ start = mid + 1; } } else{ start++; } } return false; } }