33. Search in Rotated Sorted Arr

Suppose an array sorted in ascending order 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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

题目

假设有一个升序排列的数组，但是随机的旋转了几位，具体旋转了多少不知道，现在让我们找到数组中的特定元素，返回索引值。要求时间复杂度为 O(log n)

思路

数组本身有序，但是旋转以后，就变成了局部有序。时间复杂度要求 O(log n)，即要是用二分法。所以问题就二分后怎么选取下一步区间的问题。
首先数组一分为二，获取mid，无论数组怎么旋转，肯定有半边是有序的。
所以判断一下nums[mid]和nums[0]的大小，

1. 如果nums[mid]>=nums[0]，说明数组左边是升序的，再以此为前提，继续判断：
   • nums[0]<=target<nums[mid]：则在[0,mid-1]里找;
   • 否则在[mid+1,len-1]里找。
2. 如果nums[mid]<nums[0]，说明数组右边是升序的，再以此为前提，继续判断：
   • nums[len]>=target>nums[mid]：则在[mid+1,len-1]里找;
   • 否则在[0,mid-1]里找

最后注意一下边界条件：mid可能会等于0，target也可能等于每一次缩小范围的边界上的数，所以可以加以判断，减少计算

代码

int len=nums.length;
        int l=0;
        int r=len-1;
        while (l<=r) {
            int mid=(l+r)/2;
            if (nums[mid]==target) {
                return mid;
            }
            if (nums[mid]>=nums[0]) {//左半边是递增的
                if (target==nums[l]) {
                    return l;
                }
                if (nums[mid]>target&&target>nums[0]) {//在左边找
                    r=mid-1;
                }else {
                    l=mid+1;//在右边找
                }
            }else {//右半边是递增的
                if (target==nums[r]) {
                    return r;
                }
                if (nums[mid]<target&&target<nums[len-1]) {
                    l=mid+1;
                }else {
                    r=mid-1;
                }
            }
        }
        return -1;