【数组】B054_搜索旋转排序数组（二分找单调区间）

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).

Input: nums &＃61; [4,5,6,7,0,1,2], target &＃61; 0
Output: 4

二、Solution

方法一&＃xff1a;二分

• 朴素的二分搜索要求数组是单调的&＃xff0c;而经过旋转的数组必定具有两种单调性。所以如何找到单调区间成为本题重点&＃xff0c;本题可划分为几步&＃xff1a;
  • 先找到一个连续递增区间。
  • 从递增区间里面再次确定左右边界。

边界错误&＃xff1a;这里需要注意的是&＃xff0c;当出现等于 &＃61; 的情况&＃xff0c;我们依旧要把边界移动&＃xff0c;否则&＃xff0c;会进入死循环…&＃x1f602;

public int search(int[] A, int t) {int l &＃61; 0, r &＃61; A.length-1;while (l <&＃61; r) {int m &＃61; (l &＃43; r) >>> 1;if (A[m] &＃61;&＃61; t)return m;if (A[l] <&＃61; A[m]) {if (A[l] <&＃61; t && t <&＃61; A[m]) r &＃61; m - 1;else l &＃61; m &＃43; 1;} else {if (t >&＃61; A[m] && t <&＃61; A[r]) l &＃61; m &＃43; 1;else r &＃61; m;}}return -1;
}


复杂度分析

• 时间复杂度&＃xff1a;$O(logN)$&＃xff0c;
• 空间复杂度&＃xff1a;$O(1)$&＃xff0c;