hot100 33.搜索旋转排序数组

思路把某个数x与最后一个数nums[n - 1]比大小。1.如果x nums[n - 1]那么可以得出结论1nums一定被分成左右两个递增段2第一段的所有元素均大于第二段的所有元素3x在第一段。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; // 开区间-1n - 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 target2如果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; // 开区间-1n - 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(); } }