一、题目描述给定一个元素互不相同、原本按升序排列的整数数组nums。数组在传入函数前可能在某个未知下标处发生了旋转。例如原数组[0,1,2,4,5,6,7]在下标3处旋转后可能变成[4,5,6,7,0,1,2]再给定一个目标值target如果它存在于数组中则返回对应下标否则返回-1。题目要求时间复杂度为O(log n)。普通升序数组可以直接二分查找但旋转后的数组不再整体有序因此不能直接套用标准模板。截图中的解决方案分为两步先找到最小值下标将数组划分成两个升序区间再确定目标值属于哪一段并执行普通二分查找。二、旋转数组的结构观察数组[4,5,6,7,0,1,2]虽然它整体不是升序但可以按照最小值0的位置拆成两段[4,5,6,7] [0,1,2]这两个子区间内部都保持升序。因此只要先找到最小值所在下标minIndex就能得到两个可进行二分查找的区间[0, minIndex - 1] [minIndex, nums.length - 1]所以本题可以拆成两个熟悉的问题二分查找旋转数组中的最小值在确定的升序区间中二分查找target。三、第一步找到最小值下标使用left和right表示当前搜索范围每次取中间位置mid并将nums[mid]与nums[right]比较。1.nums[mid] nums[right]if (nums[mid] nums[right]) { left mid 1; }这说明mid位于旋转点左侧的较大升序段中最小值必然在mid的右边因此可以排除[left,mid]。例如[4,5,6,7,0,1,2] ↑ ↑ mid right此时7 2最小值一定在右半部分。2.nums[mid] nums[right]else if (nums[mid] nums[right]) { right mid; }这说明mid位于包含最小值的右侧升序段中最小值可能正是nums[mid]也可能在它左边所以不能排除mid应令right mid。3.nums[mid] nums[right]else { right--; }本题已说明数组元素互不相同因此正常情况下不会进入这个分支。截图保留right--可以兼容数组存在重复元素的扩展场景相等时无法判断最小值在哪一侧只排除最右侧的一个重复元素。循环条件使用while (left right)当left right时搜索范围中只剩一个位置该位置就是最小值下标。四、第二步判断目标值属于哪一段找到minIndex后旋转数组已经被划分成两个升序区间。接下来需要判断target应该在哪一段查找。令int right nums.length - 1;由于nums[right]是第二个升序区间的最大值可以将target与它比较。1.nums[right] target目标值大于第二段中的最大值所以不可能在第二段只能在第一段return searchBinary(nums, target, 0, minIndex - 1);2.nums[right] target结合题目的旋转结构目标值若存在应在以最小值开头的第二段中查找return searchBinary(nums, target, minIndex, right);如果target比数组最小值还小虽然也会进入第二段搜索但普通二分最终会返回-1。3.nums[right] target最后一个元素正好就是目标值可以直接返回return right;这种判断方式避免了额外比较nums[0]并与截图中的实现保持一致。五、第三步在升序区间中二分查找确定目标区间后剩下的就是标准二分查找。本文使用闭区间[left,right]所以循环条件为while (left right)如果中间元素小于目标值搜索右侧如果中间元素大于目标值搜索左侧如果相等直接返回mid。if (nums[mid] target) { left mid 1; } else if (nums[mid] target) { right mid - 1; } else { return mid; }区间耗尽仍未命中说明目标值不存在返回-1。六、完整 Java 代码下面的代码严格采用截图中的“先找最小值再选择区间最后普通二分”的结构class Solution { public int search(int[] nums, int target) { // 找到最小值下标从而划分出两个升序区间 int minIndex findMin(nums); int right nums.length - 1; // target 大于第二段最大值只可能位于第一段 if (nums[right] target) { return searchBinary(nums, target, 0, minIndex - 1); } else if (nums[right] target) { // target 若存在应位于第二段 return searchBinary(nums, target, minIndex, right); } // nums[right] target return right; } // 在指定闭区间中执行标准二分查找 private int searchBinary(int[] nums, int target, int left, int right) { while (left right) { int mid left ((right - left) 1); if (nums[mid] target) { left mid 1; } else if (nums[mid] target) { right mid - 1; } else { return mid; } } return -1; } // 查找旋转数组中最小值所在的下标 private int findMin(int[] nums) { int left 0; int right nums.length - 1; while (left right) { int mid left ((right - left) 1); if (nums[mid] nums[right]) { // mid 位于左侧较大升序段 left mid 1; } else if (nums[mid] nums[right]) { // mid 位于包含最小值的升序段 right mid; } else { // 本题元素不重复该分支用于兼容重复元素 right--; } } return left; } }七、复杂度分析findMin使用二分查找定位最小值时间复杂度为O(log n)searchBinary又执行一次二分查找时间复杂度也是O(log n)。两者顺序执行O(log n) O(log n) O(log n)算法只使用常数个变量因此空间复杂度为O(1)。需要注意如果扩展到存在大量重复元素的数组right--可能使findMin在最坏情况下退化为O(n)但本题元素互不相同不存在该问题。八、常见错误1. 找最小值时写成right mid - 1当nums[mid] nums[right]时mid本身可能就是最小值所以必须保留它写成right mid。2. 使用错误的循环条件findMin的目标是让两个指针相遇应使用left right普通二分使用闭区间需要使用left right。3. 第一段的右边界写成minIndex最小值属于第二段第一段应为[0,minIndex - 1]。否则两个区间会发生重叠。4. 忘记处理未旋转数组例如[1,2,3,4]的最小值下标是0。此时第一段为[0,-1]是空区间若目标值大于nums[right]的情况不会出现其余目标会进入第二段[0,right]代码仍能正确运行。九、总结搜索旋转排序数组的关键是认识到旋转只破坏了整体有序性却保留了两个局部升序区间。本解法先通过findMin定位最小值下标将数组划分为两段再比较target与最后一个元素选择可能包含目标值的升序区间最后使用标准二分查找得到答案。