LeetCode 面试题 10.03. 搜索旋转数组

文章目录

一、题目
二、C# 题解

一、题目

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
输出: 8（元素5在该数组中的索引）

示例2:

输入： arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
输出： -1 （没有找到）

提示:

arr 长度范围在[1, 1000000]之间

点击此处跳转题目。

二、C# 题解

类似二分查找，但由于优先返回第一次出现的 target，因此主要思想如下：

取中间元素 arr[mid]，判断是否为 target。如果是，不直接返回，而转到步骤 2。
查找左半部分，结果记为 left。如果查找到结果（left >= 0），则直接返回 left。
若未找到，最后查找右半部分，返回结果。

上述方式类似前序遍历树结构，返回第一个查找的值。

同时，做出如下剪枝优化：

数组被旋转，则数组内所有元素都在区间 $+\infty)\cup(-\infty,arr[j]]$ 内。若 target 不在该区间内，直接返回 -1。
$\begin{aligned} & \sout{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10} & target:12 \\ \end{aligned}$
数组未被旋转（有序），则数组内所有元素都在区间 $[a rr [i], a rr [j]]$ 内。若 target 不在该区间内，直接返回 -1。
$\begin{aligned} & \sout{1, 3, 4, 5, 7, 10, 15, 16, 19, 20, 25} & target:30 \\ \end{aligned}$
mid 查找到值，即 arr[mid] == target。则只查看左枝，减去右枝。
$\begin{aligned} & \{15, 16, 19, 20, 1\}, \underline{\bold{2}}, \sout{3, 4, 5, 7, 10} & target:2 \\ \end{aligned}$
右枝有序且 target 在该区间内，则忽略左枝，只看右枝。
$\begin{aligned} & \sout{15, 16, 19, 20, 1}, \underline{2}, \{3, 4, 5, 7, 10\} & target:5 \\ \end{aligned}$

public class Solution {public int Search(int[] arr, int target) {return Partition(arr, 0, arr.Length - 1, target);}public int Partition(int[] arr, int i, int j, int target) {if (i > j) return -1; // 递归出口// 剪枝if (arr[j] < target && target < arr[i]) return -1; // case 1, 直接返回if (target < arr[i] && target > arr[j]) return -1; // case 2, 直接返回int mid = (i + j) / 2, left;if (arr[mid] == target) { // case 3, 减去右半部分left = Math.Min(Partition(arr, i, mid - 1, target), mid);return left == -1 ? mid : left;}if (arr[mid] < target && target < arr[j]) // case 4, 减去左半部分return Partition(arr, mid + 1, j, target);// 优先返回最前面的结果left = Partition(arr, i, mid - 1, target);if (left != -1) return left;return Partition(arr, mid + 1, j, target);}
}

时间：84 ms，击败 100.00% 使用 C# 的用户
内存：39.92 MB，击败 100.00% 使用 C# 的用户

还可以先用二分查找转折点 k，此时考虑起点为 k 终点为 k - 1 的循环数组，即，从 [k, j] 续上 [i, k - 1] 的有序数组，对其使用二分查找第一个元素。详细代码这里就不附上了。

$\begin{aligned} & \hspace{5.7em} \Rsh k \\ & 15, 16, 19, 20, \underline{1}, 2, 3, 4, 5, 7, 10 & target:5 \\ & \hspace{5.7em} \Downarrow\\ & -,\ -,\ -,\ -, \hspace{0.1em} \underline{1}, 2, 3, 4, 5, 7, 10, 15, 16, 19, 20 & target:5 \\ \end{aligned}$