搜索旋转排序数组（33）

题目

给你一个整数数组 nums ，和一个整数 target 。

该整数数组原本是按升序排列，但输入时在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

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

提示

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• nums 肯定会在某个点上旋转
• -10^4 <= target <= 10^4

算法

这一题类似上一题（第153题：寻找旋转排序数组中的最小值）的思路

二分查找

因为按照中点mid划分后的，总会有一部分必然是递增的，所以我们就在这个必然递增的部分上判断target是否落在这个区间（因为不递增（有断点不连续）的部分不好判断，但是如果target不在这个递增区间，那么必然在另一个区间）：

• 如果中点nums[mid]是目标target，直接返回mid
• 如果mid右侧递增（nums[mid]<nums[end]），我们判断target是否落在右侧：
  • 如果target在(nums[mid], nums[end]]范围内，那么将start收缩到mid+1
  • 否则target必然在另一个区间，我们将end收缩到mid-1
• 如果mid左侧递增（nums[mid]>nums[end]），我们判断target是否落在左侧：
  • 如果target在[nums[0], nums[mid])范围内，那么将end收缩到mid-1
  • 否则target必然在另一个区间，将start收缩到mid+1

export const search = (nums, target) => {
	let start = 0,
		end = nums.length - 1;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		if (nums[mid] === target) return mid;
		// 如果右侧是递增的
		else if (nums[mid] < nums[end]) {
			if (nums[mid] < target && target <= nums[end]) start = mid + 1;
			else end = mid - 1;
		}
		// 左侧是递增的
		else {
			if (nums[mid] > target && target >= nums[start]) end = mid - 1;
			else start = mid + 1;
		}
	}
	return -1;
};

另一种二分查找

关于目标点target和mid的关系，分为四种：

• mid左侧是连续的区间，target也在左侧
• mid右侧是连续的区间，target也在右侧
• mid左侧是连续的区间（右侧不连续），target在右侧
• mid右侧是连续的区间（左侧不连续），target在左侧

对于前两种情况，我们直接使用二分查找即可

对于后两种情况，我们将端点收缩到中点mid后继续判断

这种方法思想类似于第一种，只是引入了Infinity和-Infinity来辅助判断

export const search = (nums, target) => {
	let start = 0,
		end = nums.length - 1;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		if (nums[mid] === target) return mid;
		if (nums[mid] < nums[0] && target >= nums[0]) nums[mid] = Infinity;
		if (nums[mid] >= nums[0] && target < nums[0]) nums[mid] = -Infinity;
		if (target > nums[mid]) start = mid + 1;
		else if (target < nums[mid]) end = mid - 1;
	}
	return -1;
};