81. 搜索旋转排序数组 II

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

题目

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true iftarget is innums , orfalse if it is not innums .

You must decrease the overall operation steps as much as possible.

Example 1:

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

Output: true

Example 2:

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

Output: false

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums is guaranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

题目大意

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

解题思路

可以使用修改版的二分查找算法来解决这个问题。

可以定义两个指针 left 和 right，分别指向数组的起始和结束位置。在每一步查找中，计算中间位置 mid。如果 nums[mid] 等于目标值，那么直接返回 true。

然后，需要处理数组被旋转的情况。在正常的有序数组中，左半部分的元素总是小于等于右半部分的元素。如果 nums[left] <= nums[mid]，说明左半部分是有序的。在这种情况下，可以判断目标值是否在左半部分，如果是，则将 right 指针移到 mid - 1 处；否则，将 left 指针移到 mid + 1 处。

反之，如果 nums[left] > nums[mid]，说明右半部分是有序的。在这种情况下，可以判断目标值是否在右半部分，如果是，则将 left 指针移到 mid + 1 处；否则，将 right 指针移到 mid - 1 处。

通过不断缩小搜索范围，最终可以找到目标值或者确定不存在。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
	let left = 0;
	let right = nums.length - 1;
	while (left <= right) {
		const mid = Math.floor((right - left) / 2) + left;
		if (nums[left] <= nums[mid]) {
			if (nums[mid] > target) {
				right = mid - 1;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else if (nums[mid] == target) {
				return true;
			}
		} else {
			if (nums[mid] > target) {
				right = mid - 1;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else if (nums[mid] == target) {
				return true;
			}
		}
	}
	return false;
};

相关题目

题号	标题	题解	标签	难度
33	搜索旋转排序数组	[✓]	数组 二分查找