33. 搜索旋转排序数组
给你一个升序排列的整数数组 nums ，和一个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1
提示：
1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 nums 中的每个值都 独一无二 nums 肯定会在某个点上旋转 -10^4 <= target <= 10^4
思路一：暴力法
遍历数组，分别判断每个元素是否等于target
复杂度分析：
时间复杂度：O(n)。没有利用数组部分有序的特点，遍历了整个数组，所以时间复杂度为O(n)。 空间复杂度：O(1)。思路二：三次二分查找
二分法找到旋转点，实现思路可以参考：剑指offer 6.旋转数组的最小数字 & 剑指 Offer 11. 旋转数组的最小数字
接下来二分法在前半段有序数组区间中找target；
如果在前半段区间没找到，则二分法在后半段有序数组区间中找target；
都没找到， 返回-1
1 class Solution {
2 public int search(int[] nums, int target) {
3
4 int len = nums.length;
5 // 二分法找到旋转点
6 int rotate = 0;
7 int left = 0, right = len - 1, mid;
8 while(left < right){
9 mid = (left + right) / 2;
10 if(nums[mid] > nums[right]){ // 说明mid在前半段区间中
11 left = mid + 1;
12 }else if(nums[mid] < nums[right]){ // 说明mid在后半段区间中
13 right = mid;
14 }else{
15 right--; // 无法确定mid在哪个区间，right--
16 }
17 }
18 rotate = left;
19 System.out.println(rotate);
20 // 二分法在前半段有序数组区间中找target
21 left = 0;
22 right = rotate - 1;
23 while(left <= right){
24 mid = (left + right) / 2;
25 if(target > nums[mid]){
26 left = mid + 1;
27 }else if(target < nums[mid]){
28 right = mid - 1;
29 }else{
30 return mid;
31 }
32 }
33 // 二分法在后半段有序数组区间中找target
34 left = rotate;
35 right = len - 1;
36 while(left <= right){
37 mid = (left + right) / 2;
38 if(target > nums[mid]){
39 left = mid + 1;
40 }else if(target < nums[mid]){
41 right = mid - 1;
42 }else{
43 return mid;
44 }
45 }
46
47 // 都没找到， 返回-1
48 return -1;
49 }
50 }
leetcode 执行用时：4 ms > 15.28%, 内存消耗：37.8 MB > 92.01%
复杂度分析：
时间复杂度：O(logn)。三个循环，都是二分查找，所以时间复杂度为O(3logn), 在数组重复元素很多时，第一个循环查找旋转点因为无法判断当前元素属于前后哪个区间，使用rigiht-1来处理，所以可能退化成O(n)的复杂度，但是因为题目说明了数组元素不重复，所以这个算法的复杂度并不会退化成O(n)。 空间复杂度：O(1)。思路二：只需一次二分查找
1 class Solution {
2 public int search(int[] nums, int target) {
3
4 int len = nums.length;
5 // 二分法找到旋转点
6 // int rotate = 0;
7 int left = 0, right = len - 1, mid;
8 while(left <= right){
9 mid = (left + right) / 2;
10 if(nums[mid] == target){
11 return mid;
12 }
13 if(nums[mid] > nums[right]){ // 说明mid在前半段区间中
14 // 判断target在[left, mid)之间还是在[mid, right]之间
15 if(target >= nums[left] && target < nums[mid]){
16 right = mid - 1;
17 }else{
18 left = mid + 1;
19 }
20 }else if(nums[mid] < nums[right]){ // 说明mid在后半段区间中
21 // 判断target在[mid, right],之间还是在[left, mid]之间
22 if(target > nums[mid] && target <= nums[right]){
23 left = mid + 1;
24 }else{
25 right = mid;
26 }
27 }else{
28 right--;
29 }
30 }
31 // 都没找到， 返回-1
32 return -1;
33 }
34 }
leetcode 执行用时：0 ms > 100.00%, 内存消耗：37.8 MB > 90.36%