题目地址(33. 搜索旋转排序数组)

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目描述

  1. 整数数组 nums 按升序排列，数组中的值 互不相同 。
  3. 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
  5. 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
  9. 示例 1：
  11. 输入：nums = [4,5,6,7,0,1,2], target = 0
  12. 输出：4
  15. 示例 2：
  17. 输入：nums = [4,5,6,7,0,1,2], target = 3
  18. 输出：-1
  20. 示例 3：
  22. 输入：nums = [1], target = 0
  23. 输出：-1
  28. 提示：
  30. 1 <= nums.length <= 5000
  31. -10^4 <= nums[i] <= 10^4
  32. nums 中的每个值都 独一无二
  33. 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  34. -10^4 <= target <= 10^4
  38. 进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

前置知识


公司

  • 暂无

思路

题目要求 O(logN)O(logN) 的时间复杂度，基本可以断定本题是需要使用二分查找，怎么分是关键。
由于题目说数字了无重复，举个例子：
1 2 3 4 5 6 7 可以大致分为两类，
第一类 2 3 4 5 6 7 1 这种，也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5。
这种情况下，前半部分有序。因此如果 nums[start] <=target第二类 6 7 1 2 3 4 5 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2。
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]，则在后半部分找，否则去前半部分找。

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int length = nums.length;
  4.         if (length == 1) {
  5.             return nums[0] == target ? 0 : -1;
  6.         }
  7.         int left = 0;
  8.         int right = length - 1;
  9.         while (left <= right) {
  10.             int mid = (right + left) / 2;
  11.             if (nums[mid] == target) {
  12.                 return mid;
  13.             }
  14.             //中间值大于等于左边的值 举个例子 数组旋转后的顺序为 5 6 7 1 3 nums[mid] =7 tar = 6
  15.             if (nums[mid] >= nums[left] ) {
  16.                 //找出 [5 , 6]的元素 把right变为mid-1 因为上面判断过mid是不是tar了 所以不包含
  17.                 if (target < nums[mid] && target >= nums[left]) {
  18.                     right = mid - 1;
  19.                 }else{
  20.                     //否则就在[1,3]里
  21.                     left = mid + 1;
  22.                 }
  23.             }else{
  24.                 //举个例子 数组旋转后的顺序为 7 1 3 5 6  nums[mid] =3 tar = 6
  25.                 //找出 [5 , 6]的元素 把left 变为mid+1
  26.                 if (target > nums[mid] && target <= nums[right]) {
  27.                     left = mid + 1;
  28.                 }else {
  29.                     //否则就在[7,1]里
  30.                     right = mid - 1;
  31.                 }
  32.             }
  33.         }
  34.         return -1;
  35.     }
  36. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：33. 搜索旋转排序数组 - 图1
  • 空间复杂度：33. 搜索旋转排序数组 - 图2#card=math&code=O%28n%29&id=F4bBi)