LeetCode 第 33 题：“搜索旋转排序数组”题解
题解地址：二分法（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：33. 搜索旋转排序数组。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
二分法（Python 代码、Java 代码）
题目给出的是“旋转排序数组”，是“部分有序数组”，我们同样可以一次排除一半或者一半以上元素的方法，即二分查找法。
二分查找法的本质是排除法，二分只是手段，二分保证了“熵”最大，即在没有任何有效信息的时候，平分是最好的方案。
思路清楚了以后，我们就得确定“有序数组”存在在“原始数组”的哪个子区间里，下面提供了两个比较标准：
1、中间元素和左边界比较；
2、中间元素和右边界比较。
由这两个比较标准就能写出两版不同的代码。
方法：二分查找
二分查找法的模板我写在了「力扣」第 35 题：“搜索插入位置”的题解《特别好用的二分查找法模板（Python 代码、Java 代码）》。
注意：以下代码中的边界部分，是“小于等于”还是“小于”，是“大于等于”还是“等于”，需要让两个不同情况的分支逻辑一样，二分算法才有效，这一点我说得可能不太清楚，请大家自行体会。
情况 1：中间元素和右边界比较
参考代码 1：
Python 代码：
from typing import List
# 中间元素和右边界比较
class Solution:
def search(self, nums: List[int], target: int) -> int:
size = len(nums)
if size == 0:
return -1
left = 0
right = size - 1
while left < right:
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
if nums[mid] < nums[right]:
# [7,8,9,1,2,3,4,5,6] ，后半部分有序
if nums[mid] <= target <= nums[right]:
left = mid
else:
right = mid - 1
else:
# [4,5,6,7,8,9,0,1,2]，前半部分有序
if nums[left] <= target <= nums[mid - 1]:
right = mid - 1
else:
left = mid
# 后处理
return left if nums[left] == target else -1
Java 代码：
public class Solution2 {
// 中间元素和右边界比较
public int search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
int left = 0;
int right = len - 1;
// 注意：这里是等于
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] > nums[right]) {
// 前有序，包括中间数
// 6 7 8 9 1 2
if (nums[left] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
// 后有序，包括中间数
// 6 7 1 2 3 4 5 6
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
}
if (nums[left] == target) {
return left;
}
return -1;
}
}
复杂度分析：
- 时间复杂度：，这里 是数组的长度，在循环中一次排除一半，因此时间复杂度是对数级别的。
- 空间复杂度：，使用到的临时变量的个数是常数。
情况 2：中间元素和左边界比较
参考代码 2：
Python 代码：
from typing import List
# 中间元素和左边界比较
class Solution:
def search(self, nums: List[int], target: int) -> int:
size = len(nums)
if size == 0:
return -1
left = 0
right = size - 1
while left < right:
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
if nums[mid] < nums[left]:
# [7,8,9,1,2,3,4,5,6] ，后半部分有序
if nums[mid] <= target <= nums[right]:
left = mid
else:
right = mid - 1
else:
# [4,5,6,7,8,9,0,1,2]，前半部分有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid
# 后处理
return left if nums[left] == target else -1
Java 代码：
public class Solution3 {
// 中间元素和左边界比较
public int search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
int left = 0;
int right = len - 1;
// 注意：这里是等于
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (nums[mid] > nums[left]) {
// 前有序，包括中间数
// 1 2 6 7 8 9
// 6 7 8 9 1 2
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid;
}
} else {
// 后有序，包括中间数
// 8 9 1 2 6 7
if (nums[mid] <= target && target <= nums[right]) {
left = mid;
} else {
right = mid - 1;
}
}
}
if (nums[left] == target) {
return left;
}
return -1;
}
public static void main(String[] args) {
int[] nums = {3, 1};
int target = 1;
Solution3 solution = new Solution3();
int search = solution.search(nums, target);
System.out.println(search);
}
}
复杂度分析：
（同上。）