33. 搜索旋转排序数组

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] ( 0-indexed ). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index oftarget if it is innums , or-1 if it is not innums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Example 3:

Input: nums = [1], target = 0

Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

题目大意

整数数组 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. 首先，数组依然可以通过中间值 mid 将左右部分分为有序和无序两部分。

2. 每次找到中间位置 mid，先检查 nums[mid] 是否等于目标值。如果相等，直接返回索引。

3. 通过 nums[left] 和 nums[mid] 的大小关系来判断哪一部分是有序的。

   • 通过比较 nums[left] 和 nums[mid] 可以判断左半部分是否有序。
   • 如果 nums[left] <= nums[mid]，说明左半部分是有序的，否则右半部分有序。

4. 判断目标值的位置：

   • 如果左半部分有序，且目标值落在 nums[left] 到 nums[mid] 之间，那么缩小搜索范围至左半部分，否则去右半部分继续查找。
   • 如果右半部分有序，且目标值落在 nums[mid] 到 nums[right] 之间，那么缩小搜索范围至右半部分，否则去左半部分继续查找。

5. 不断缩小查找区间，直到找到目标值，或者使得 left > right时返回 -1。

复杂度分析

• 时间复杂度：O(log n)，这是二分查找的时间复杂度，每次查找时将搜索范围缩小一半。
• 空间复杂度：O(1)，只用了常量级的额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
	let left = 0;
	let right = nums.length - 1;

	while (left <= right) {
		let mid = Math.floor((left + right) / 2);

		// 找到目标值
		if (nums[mid] === target) {
			return mid;
		}

		// 判断左半部分是否有序
		if (nums[left] <= nums[mid]) {
			// 如果 target 在左半部分的范围内
			if (nums[left] <= target && target < nums[mid]) {
				right = mid - 1; // 缩小到左半部分
			} else {
				left = mid + 1; // 否则缩小到右半部分
			}
		}
		// 否则右半部分有序
		else {
			// 如果 target 在右半部分的范围内
			if (nums[mid] < target && target <= nums[right]) {
				left = mid + 1; // 缩小到右半部分
			} else {
				right = mid - 1; // 否则缩小到左半部分
			}
		}
	}

	// 没有找到目标值
	return -1;
};

相关题目

题号	标题	题解	标签	难度
81	搜索旋转排序数组 II	[✓]	数组 二分查找
153	寻找旋转排序数组中的最小值	[✓]	数组 二分查找
2137	通过倒水操作让所有的水桶所含水量相等 🔒		数组 二分查找