# 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```

如果直接循环遍历，复杂度是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;@SpringBootApplicationpublic 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));    }}`