JAVA练习339- 搜索旋转排序数组

题目概览

整数数组nums按升序排列，数组中的值互不相同。

在传递给函数之前，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]。

给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-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

示例 3：

输入：nums = [1], target = 0输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums中的每个值都独一无二
• 题目数据保证nums在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

来源：33. 搜索旋转排序数组 - 力扣（LeetCode）

解题分析

方法：二分法

我们可以先尝试进行二分，以 [5,6,0,1,2,3,4] 为例，第一次二分之后的子数组为 [ 5,6,0,1 ] 和 [ 2,3,4]，这样得到的子数组至少有一个时递增的，令中间索引为 mid，开始索引为 i，结束索引为 j，那么：

1. 当 nums[ mid ] == target 时，返回 mid
2. 当 nums[ mid ] > target 时，看左子数组是否为递增数组（nums[ i ] <= nums[mid] )，
   若是，则看 nums[ i ] 是否小于等于 target ，若小于等于 target 则在左子数组中，j = mid - 1；大于 target 则还在右边数组中，i = mid + 1;
   若不是，说明右子数组是递增数组，target 还在左边数组中，j = mid - 1
3. 当 nums[ mid ] < target 时，看右子数组是否为递增数组（nums[ j ] >= nums[mid] )，
   若是，则看 nums[ j ] 是否大于等于 target ，若大于等于 target 则在右子数组中，i = mid + 1；小于 target 则还在右边数组中，j = mid - 1;
   若不是，说明左子数组是递增数组，target 还在右边数组中，i = mid + 1

时间复杂度：O(logn)
空间复杂度：O(1)

class Solution { public int search(int[] nums, int target) { int n = nums.length; int i = 0, j = n-1; while(i <= j) { int mid = (i + j) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] > target) { if (nums[i] <= nums[mid] && nums[i] > target) { i = mid + 1; } else { j = mid - 1; } } else { if (nums[j] >= nums[mid] && nums[j] < target) { j = mid - 1; } else { i = mid + 1; } } } return -1; } }