面试中高频算法问题： 搜索旋转有序数组

搜索旋转有序数组

假设按升序排序的数组在某个未知点进行旋转。 （例如，数组[0,1,2,4,5,6,7]可以是[4,5,6,7,0,1,2]，返回其索引，否则-1。您可以假设数组中不存在重复元素。该算法的时间复杂度应该是O(log n)。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

答案

为了简单起见，这里数组中的最小值称为枢轴点，那我们就用上面的例子来解释一下吧。

未旋转前的数组

旋转后的数组

显然，这个枢轴点是最特别的点，因为旋转点比左边的数字越来越小 数字很小

我们知道，在我们的 常规二分查找 （即旋转数组之前）我们比较目标value 与中间元素 mid 比较，会得到以下三个结果：

(1) 如果目标值小于中间值，则中间值以及中间值右边的所有元素都必须大于目标值，所以目标只在中间的左边元素可能存在。

(2) 如果目标大于中心，那么中心以及中心左​​边的所有元素都必须小于目标，所以目标只能存在于中心右边的元素中。

(3) 如果target等于mid，则返回mid对应的下标。

对于这道题，情况比较复杂，因为转折点的位置也有影响。具体可以分为以下两种情况。

这里要强调的是，二分查找的结果是缩小范围，所以我们的目标是找出目标是在中心的左边还是右边。

(1) 情况 1：中间元素位于枢轴点的左侧

(1) 目标位于中心的左侧。

如果目标位于中间的左侧，那么显然必须满足条件：最左边的元素 >= 目标 > mid。

(2) 目标在中心的右侧

如果不满足条件(1)，则表示它在右侧

(2) 情况 2：中间元素是右侧位于枢轴点一侧或与枢轴点重合

的右侧与

重合 (1) 目标位于

的右侧 条件为显然满足 mid > target >= 右极值元素

(1) 如果不满足条件 (1)，则目标位于中心

的左侧。

当然，在上面的情况下，我们不会出现中间和目标相等的情况，因为如果相等的话，我们就只能回到底层而不进行讨论。

我们讨论了上面的不同情况。现在我们就可以直接按照上面的逻辑编写代码了。代码是：

int rotatedBinarySearch(int[] arr, int target){
 // 最左侧元素下标
 int left = 0;
 // 最右侧元素下标
 int right = arr.length - 1;
 while(left >= right){
 // 中间元素下标
 int mid = left + (right - left) / 2;
 if(arr[mid] == target){
 return mid;
 }
 // 情况1：如果中间元素在旋转点左侧
 if(arr[mid] <= arr[left]){
 //target 如果位于中间元素的左侧
 if(arr[mid] < target && target <= arr[left]){
 right = mid - 1;
 }else{
 left = mid + 1;
 }
 }
 // 情况2：中间元素在旋转点的右侧
 else{
 // target 如果位于中间元素的右侧
 if(arr[mid] > target && target >= arr[right]){
 left = mid + 1;
 }else{
 right = mid - 1;
 }
 }
 }
 return -1;
}