LeetCode 33：Search in Rotated Sorted Array

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

Example 2:

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

一开始题目旋转的意思没看太明白，其实它的意思是首先有一个已经从小到大排序号的数组，然后根据数组中某一个数字来将数组进行旋转，也就是两边进行交换，生成一个新的数组，也就是nums，然后在这个nums里查找target的值，返回index

比如，按照上面例子中的数组，简单画一下旋转大致有以下几种结果，但具体参数nums传入的是哪一种结果未知

折腾了半天，才发现题目意思理解错了，所谓旋转并不是以数组中某个数字为轴旋转，而是以一个其它的点为圆心，这样就不存不动的数字，所有结果如下 

 如果直接循环遍历，复杂度是O(n)，而题目要求是O(logn)，肯定还是得用二分法相关的，主要是判断target是在哪边，先找下特点

1：找到中间的数字nums[middle]，如果nums[middle]==target，直接返回middle

2：如果nums[middle] >= nums[left]，比如上图0，1，2，3，4的情况，这时候可以发现，左侧的都是有序的，那么假如target在左侧区间范围里，right = middle – 1；否则在右侧区间范围里，left = middle +1

3：如果nums[middle] < nums[left]，比如上图5，6，7的情况，这时候可以发现，右侧的都是有序的，那么假如target在右侧区间范围里，left = middle + 1；否则在左侧区间范围里，right = middle -1

4：如果已上最终还无法找到target，返回-1

源码如下

package com.lihuia.demo;

import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class DemoApplication {
    
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] >= nums[left]) {
                if (nums[left] <= target && target < nums[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            } else {
                if (nums[middle] < target && target <= nums[right]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] nums = {5,6,7,4,0,1,2,3};
        System.out.println(search(nums, 0));
    }
}