33-搜索旋转排序数组

题目描述

原题链接

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

数组 nums 旋转以后，得到一个升序数组。如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1 。

示例 1：

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

题解

"搜索旋转排序数组" 是一道经典的二分查找问题，但它带有一个变化：数组在某个未知的点上被旋转。这个问题通常是这样描述的：给定一个在某个点上被旋转的升序数组，和一个目标值，你需要在数组中找到目标值的位置，如果不存在则返回 -1。

解决这个问题的关键是使用二分查找，但由于数组被旋转，需要添加额外的逻辑来确定搜索的方向。以下是解决这个问题的步骤：

1. 找到中间元素：首先找到数组的中间元素。

2. 判断哪一侧是有序的：由于数组原本是排序的，所以即使它被旋转，至少有一半仍然是有序的。判断中间元素是位于有序的部分还是无序的部分。

提示

要判断中间元素是位于有序部分还是无序部分，可以通过比较中间元素与数组两端的元素来实现。在一个部分旋转的数组中，至少有一个半段（左半段或右半段）是有序的。以下是如何判断的步骤：

1. 比较中间元素和左端元素：

   • 如果中间元素大于等于左端元素，这表明左半段是有序的。例如，在数组 [4, 5, 6, 7, 0, 1, 2] 中，如果中间元素是 7，由于 7 > 4，左半段 [4, 5, 6, 7] 是有序的。
   • 如果不是这种情况，则右半段是有序的。

2. 比较中间元素和右端元素：

   • 同样的逻辑也适用于中间元素和右端元素的比较。如果中间元素小于等于右端元素，这表明右半段是有序的。
   • 如果不是这种情况，则左半段是有序的。

这种方法的关键在于，由于原始数组是升序排列的，所以即使它被部分旋转，数组的一半仍然会保持升序。通过判断哪一半是有序的，我们可以更有效地决定如何调整二分查找的范围，以快速找到目标元素。

4. 决定搜索范围：

   • 如果中间元素等于目标值，直接返回该位置。
   • 如果中间元素位于有序部分：
     • 如果目标值位于中间元素和有序部分的起始元素之间，对这一区间进行二分查找。
     • 否则，在另一半区间进行查找。
   • 如果中间元素位于无序部分，对另一半区间采用同样的逻辑。

5. 递归或迭代直到找到目标值或确定目标值不存在。

以下是使用 Go 语言实现的示例代码：

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right-left)/2 + left

		if nums[mid] == target {
			return mid
		}

		if nums[left] <= nums[mid] {
			// 左边有序
			if nums[left] <= target && target <= nums[mid] {
				// 在左边
				right = mid - 1
			} else {
				// 在右边
				left = mid + 1
			}
		} else {
			// 右边有序
			if nums[mid] <= target && target <= nums[right] {
				// 在右边
				left = mid + 1
			} else {
				// 在左边
				right = mid - 1
			}
		}
	}

	return -1
}

在这段代码中，search 函数接受一个旋转后的数组 nums 和一个目标值 target。它使用二分查找来找到目标值的位置。如果找到了目标值，它会返回目标值的索引；如果没有找到，它会返回 -1。