hot100 33.搜索旋转排序数组

思路：把某个数x与最后一个数nums[n - 1]比大小。

1.如果x > nums[n - 1]，那么可以得出结论：

（1）nums一定被分成左右两个递增段；

（2）第一段的所有元素均大于第二段的所有元素；

（3）x在第一段。

2.如果x <= nums[n - 1]，那么x一定在第二段（或者nums就是递增数组，此时只有一段）。

一、方法一：两次二分

1.首先，找到nums的最小值的下标i。

2.然后分类讨论：

（1）如果target > nums[n - 1]，那么target一定在第一段[0,i - 1]中，于是在[0,i - 1]中二分查找target。

（2）如果target <= nums[n - 1]，那么：

（a）如果i = 0，说明nums是递增的，直接在[0,n - 1]中二分查找target。

（b）如果i > 0，说明target一定在第二段[i,n - 1]中，在[i,n - 1]中二分查找target。

（c）这两种情况可以合并成在[i, n - 1]中二分查找target。

3.复杂度分析：

（1）时间复杂度：O(logn)，其中n为nums的长度。

（2）空间复杂度：O(1)。

注意：

（1）第一个函数（findMin）的循环条件是while(left < right)：这是因为最小值一定存在，这个循环的终止条件是left == right，此时这个位置就是最小值（最小值是一定存在的，所以最终要收缩到单个点，且此时return left 或return right都对）。

（2）第二个函数（lowerBound）的循环条件是while(left <= right)：这是因为target可能不存在，这个循环的终止条件是left > right，此时区间为空，target不存在（找不到target的情况下，return -1）。

附代码（下面代码用的闭区间二分，用其他二分写法也是可以的）：

class Solution { public int search(int[] nums, int target) { int n = nums.length; if(n == 0){ return -1; } int i = findMin(nums); if(target > nums[n - 1]){ // target 在第一段 return lowerBound(nums,0,i - 1,target); // 闭区间[0,i - 1] } // target在第二段 return lowerBound(nums,i,n - 1,target); // 闭区间[i,n - 1] } private int findMin(int[] nums){ // 寻找旋转排序数组中的最小值（即第一段和第二段的分界点），返回的是下标 int n = nums.length; int left = 0; int right = n - 1; //闭区间[0,n - 1] while(left < right){ // 闭区间不为空 int mid = (right - left) / 2 + left; // <= 是为了处理最大元素是重复元素的情况 if(nums[mid] <= nums[n - 1]){ right = mid; // 最小值在左侧（含mid），因为mid位置也满足小于n - 1位置的元素，不能排除 }else{ left = mid + 1; // 最小值在右侧 } } return left; // 或return right; } // 有序数组中找target的下标 private int lowerBound(int[] nums,int left,int right,int target){ while(left <= right){ // 闭区间不为空 // 循环不变量： // nums[right] >= target // nums[left] < target int mid = (right - left) / 2 + left; if(nums[mid] == target){ return mid; } if(nums[mid] < target){ left = mid + 1; // 范围缩小到[mid + 1,right] }else{ right = mid - 1; // 范围缩小到[left,mid - 1] } } return -1; } }

二、方法二：一次二分

1.思路：设x = nums[mid]是我们现在二分取到的数。我们需要判断x和target的位置关系，谁在左边，谁在右边？

2.复杂度分析：

（1）时间复杂度：O(logn)，其中n为nums的长度。

（2）空间复杂度：O(1)。

（一）写法一：

1.分类讨论：

（1）如果x和target在不同的递增段：

（a）如果target在第一段，x在第二段，说明target在x的左边；

（b）如果x在第一段，target在第二段，说明target在x的右边；

（2）如果x和target在相同的递增段：那么和lowerBound函数一样，比较x和target的大小即可。

附代码（下面代码用的开区间二分，用其他二分写法也是可以的）：

class Solution { public int search(int[] nums, int target) { int last = nums[nums.length - 1]; int left = -1; int right = nums.length - 1; // 开区间（-1，n - 1） while(left + 1 < right) { // 开区间不为空 int mid = (left + right) >>> 1; int x = nums[mid]; if(target > last && x <= last){ // target在第一段，x在第二段 right = mid; //下轮循环去左边找 }else if(x > last && target <= last){ // x在第一段，target在第二段 left = mid; //下轮循环去右边找 }else if(x >= target){ // 否则，x和target在同一段，这就和方法一的lowerBound一样了 right = mid; }else{ left = mid; } } return nums[right] == target ? right : -1; } }

（二）写法二：

1.下面只讨论target在x左边，或者x = target的情况，其余情况target一定在x的右边。

（1）如果x > nums[n - 1]，说明x在第一段中，那么target也必须在第一段中（否则target一定在x的右边），且x必须大于等于target。写成代码就是target > nums[n - 1] && x >= target；

（2）如果x <= nums[n - 1]，说明x在第二段中（或者nums只有一段），那么target可以在第一段，也可以在第二段。

（a）如果target在第一段，那么target一定在x左边。

（b）如果target在第二段，那么x必须大于等于target。

（c）写成代码就是target > nums[n - 1] || x >= target。

（3）根据这两种情况，去判断x和target的位置关系，从而不断地缩小target所在位置的范围，二分找到target。

附代码：

class Solution { public int search(int[] nums, int target) { int left = -1; int right = nums.length - 1; // 开区间（-1，n - 1） while(left + 1 < right){ // 开区间不为空 int mid = (left + right) >>> 1; if(check(nums,target,mid)){ right = mid; }else{ left = mid; } } return nums[right] == target ? right : -1; } private boolean check(int[] nums,int target,int i){ int last = nums[nums.length - 1]; int x = nums[i]; if(x > last){ return target > last && x >= target; } return target > last || x >= target; } }

ACM模式：

import java.util.Scanner; class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } int i = findMin(nums); if (target > nums[n - 1]) { return lowerBound(nums, 0, i - 1, target); } return lowerBound(nums, i, n - 1, target); } private int findMin(int[] nums) { int n = nums.length; int left = 0; int right = n - 1; while (left < right) { int mid = (right - left) / 2 + left; if (nums[mid] <= nums[n - 1]) { right = mid; } else { left = mid + 1; } } return left; } private int lowerBound(int[] nums, int left, int right, int target) { while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数组长度 int n = scanner.nextInt(); // 读取数组元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 读取目标值 int target = scanner.nextInt(); // 搜索目标值 Solution solution = new Solution(); int result = solution.search(nums, target); System.out.println(result); scanner.close(); } }

构造测试用例：

import java.util.*; class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } int i = findMin(nums); if (target > nums[n - 1]) { return lowerBound(nums, 0, i - 1, target); } return lowerBound(nums, i, n - 1, target); } private int findMin(int[] nums) { int n = nums.length; int left = 0; int right = n - 1; while (left < right) { int mid = (right - left) / 2 + left; if (nums[mid] <= nums[n - 1]) { right = mid; } else { left = mid + 1; } } return left; } private int lowerBound(int[] nums, int left, int right, int target) { while (left <= right) { int mid = (right - left) / 2 + left; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } } public class Main { // 手动构造测试用例 public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1：旋转数组，目标在左半部分 // 数组: [4,5,6,7,0,1,2], target = 0 // 期望输出: 4 int[] nums1 = {4, 5, 6, 7, 0, 1, 2}; int target1 = 0; int result1 = solution.search(nums1, target1); System.out.println("测试用例1 - 数组: " + Arrays.toString(nums1) + ", 目标: " + target1); System.out.println("结果索引: " + result1); System.out.println(); // 测试用例2：旋转数组，目标在右半部分 // 数组: [4,5,6,7,0,1,2], target = 5 // 期望输出: 1 int[] nums2 = {4, 5, 6, 7, 0, 1, 2}; int target2 = 5; int result2 = solution.search(nums2, target2); System.out.println("测试用例2 - 数组: " + Arrays.toString(nums2) + ", 目标: " + target2); System.out.println("结果索引: " + result2); System.out.println(); // 测试用例3：旋转数组，目标不存在 // 数组: [4,5,6,7,0,1,2], target = 3 // 期望输出: -1 int[] nums3 = {4, 5, 6, 7, 0, 1, 2}; int target3 = 3; int result3 = solution.search(nums3, target3); System.out.println("测试用例3 - 数组: " + Arrays.toString(nums3) + ", 目标: " + target3); System.out.println("结果索引: " + result3); System.out.println(); // 测试用例4：未旋转的数组 // 数组: [1,2,3,4,5,6,7], target = 4 // 期望输出: 3 int[] nums4 = {1, 2, 3, 4, 5, 6, 7}; int target4 = 4; int result4 = solution.search(nums4, target4); System.out.println("测试用例4 - 数组: " + Arrays.toString(nums4) + ", 目标: " + target4); System.out.println("结果索引: " + result4); System.out.println(); // 测试用例5：旋转一次（最小元素在最后） // 数组: [2,3,4,5,6,7,1], target = 1 // 期望输出: 6 int[] nums5 = {2, 3, 4, 5, 6, 7, 1}; int target5 = 1; int result5 = solution.search(nums5, target5); System.out.println("测试用例5 - 数组: " + Arrays.toString(nums5) + ", 目标: " + target5); System.out.println("结果索引: " + result5); System.out.println(); // 测试用例6：旋转一次（最小元素在开头） // 数组: [1,2,3,4,5,6,7], target = 7 // 期望输出: 6 int[] nums6 = {1, 2, 3, 4, 5, 6, 7}; int target6 = 7; int result6 = solution.search(nums6, target6); System.out.println("测试用例6 - 数组: " + Arrays.toString(nums6) + ", 目标: " + target6); System.out.println("结果索引: " + result6); System.out.println(); // 测试用例7：只有一个元素的数组，目标存在 // 数组: [1], target = 1 // 期望输出: 0 int[] nums7 = {1}; int target7 = 1; int result7 = solution.search(nums7, target7); System.out.println("测试用例7 - 数组: " + Arrays.toString(nums7) + ", 目标: " + target7); System.out.println("结果索引: " + result7); System.out.println(); // 测试用例8：只有一个元素的数组，目标不存在 // 数组: [1], target = 2 // 期望输出: -1 int[] nums8 = {1}; int target8 = 2; int result8 = solution.search(nums8, target8); System.out.println("测试用例8 - 数组: " + Arrays.toString(nums8) + ", 目标: " + target8); System.out.println("结果索引: " + result8); System.out.println(); // 测试用例9：空数组 // 数组: [], target = 1 // 期望输出: -1 int[] nums9 = {}; int target9 = 1; int result9 = solution.search(nums9, target9); System.out.println("测试用例9 - 数组: " + Arrays.toString(nums9) + ", 目标: " + target9); System.out.println("结果索引: " + result9); System.out.println(); // 测试用例10：旋转数组，目标是最小值 // 数组: [5,6,7,8,9,1,2,3,4], target = 1 // 期望输出: 5 int[] nums10 = {5, 6, 7, 8, 9, 1, 2, 3, 4}; int target10 = 1; int result10 = solution.search(nums10, target10); System.out.println("测试用例10 - 数组: " + Arrays.toString(nums10) + ", 目标: " + target10); System.out.println("结果索引: " + result10); System.out.println(); // 测试用例11：旋转数组，目标是最大值 // 数组: [5,6,7,8,9,1,2,3,4], target = 9 // 期望输出: 4 int[] nums11 = {5, 6, 7, 8, 9, 1, 2, 3, 4}; int target11 = 9; int result11 = solution.search(nums11, target11); System.out.println("测试用例11 - 数组: " + Arrays.toString(nums11) + ", 目标: " + target11); System.out.println("结果索引: " + result11); System.out.println(); // 测试用例12：旋转数组，左半部分查找不到 // 数组: [4,5,6,7,0,1,2], target = 6 // 期望输出: 2 int[] nums12 = {4, 5, 6, 7, 0, 1, 2}; int target12 = 6; int result12 = solution.search(nums12, target12); System.out.println("测试用例12 - 数组: " + Arrays.toString(nums12) + ", 目标: " + target12); System.out.println("结果索引: " + result12); System.out.println(); // 测试用例13：旋转数组，右半部分查找不到 // 数组: [4,5,6,7,0,1,2], target = 1 // 期望输出: 5 int[] nums13 = {4, 5, 6, 7, 0, 1, 2}; int target13 = 1; int result13 = solution.search(nums13, target13); System.out.println("测试用例13 - 数组: " + Arrays.toString(nums13) + ", 目标: " + target13); System.out.println("结果索引: " + result13); System.out.println(); // 测试用例14：旋转两次 // 数组: [3,4,5,6,7,8,1,2], target = 8 // 期望输出: 5 int[] nums14 = {3, 4, 5, 6, 7, 8, 1, 2}; int target14 = 8; int result14 = solution.search(nums14, target14); System.out.println("测试用例14 - 数组: " + Arrays.toString(nums14) + ", 目标: " + target14); System.out.println("结果索引: " + result14); System.out.println(); // 测试用例15：旋转数组，包含重复元素（注意：题目假设无重复，但测试边界） // 数组: [2,2,2,0,2,2], target = 0 // 期望输出: 3 int[] nums15 = {2, 2, 2, 0, 2, 2}; int target15 = 0; int result15 = solution.search(nums15, target15); System.out.println("测试用例15 - 数组: " + Arrays.toString(nums15) + ", 目标: " + target15); System.out.println("结果索引: " + result15); System.out.println(); } }