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

一、题目

  搜索旋转数组。给定一个排序后的数组，包含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。
• 若未找到，最后查找右半部分，返回结果。

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

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

1. 数组被旋转，则数组内所有元素都在区间 $[arr[i],+\infty )\cup (-\infty ,arr[j]]$ 内。若 target 不在该区间内，直接返回 -1。
   15 , 16 , 19 , 20 , 25 , 1 , 3 , 4 , 5 , 7 , 10 t a r g e t : 12

   \sout15,16,19,20,25,1,3,4,5,7,10target:12" role="presentation" style="position: relative;">\sout15,16,19,20,25,1,3,4,5,7,10target:12$$\begin{array}{rlr}& \text{sout}15,16,19,20,25,1,3,4,5,7,10& target:12\end{array}$$
   ​15,16,19,20,25,1,3,4,5,7,10​​target:12​

2. 数组未被旋转（有序），则数组内所有元素都在区间 $[arr[i],arr[j]]$ 内。若 target 不在该区间内，直接返回 -1。
   1 , 3 , 4 , 5 , 7 , 10 , 15 , 16 , 19 , 20 , 25 t a r g e t : 30

   \sout1,3,4,5,7,10,15,16,19,20,25target:30" role="presentation" style="position: relative;">\sout1,3,4,5,7,10,15,16,19,20,25target:30$$\begin{array}{rlr}& \text{sout}1,3,4,5,7,10,15,16,19,20,25& target:30\end{array}$$
   ​1,3,4,5,7,10,15,16,19,20,25​​target:30​

3. mid 查找到值，即 arr[mid] == target。则只查看左枝，减去右枝。
   { 15 , 16 , 19 , 20 , 1 } , 2 ‾ , 3 , 4 , 5 , 7 , 10 t a r g e t : 2

   {15,16,19,20,1},\bold2_,\sout3,4,5,7,10target:2" role="presentation" style="position: relative;">{15,16,19,20,1},\bold2–––––––,\sout3,4,5,7,10target:2$$\begin{array}{rlr}& \{15,16,19,20,1\},\underset{\_}{\text{bold}2},\text{sout}3,4,5,7,10& target:2\end{array}$$
   ​{15,16,19,20,1},2​,3,4,5,7,10​​target:2​

4. 右枝有序且 target 在该区间内，则忽略左枝，只看右枝。
   15 , 16 , 19 , 20 , 1 , 2 ‾ , { 3 , 4 , 5 , 7 , 10 } t a r g e t : 5

   \sout15,16,19,20,1,2_,{3,4,5,7,10}target:5" role="presentation" style="position: relative;">\sout15,16,19,20,1,2–,{3,4,5,7,10}target:5$$\begin{array}{rlr}& \text{sout}15,16,19,20,1,\underset{\_}{2},\{3,4,5,7,10\}& target:5\end{array}$$
   ​15,16,19,20,1​,2​,{3,4,5,7,10}​target:5​

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

---

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

↱ k 15 , 16 , 19 , 20 , 1 ‾ , 2 , 3 , 4 , 5 , 7 , 10 t a r g e t : 5 ⇓ − ,   − ,   − ,   − , 1 ‾ , 2 , 3 , 4 , 5 , 7 , 10 , 15 , 16 , 19 , 20 t a r g e t : 5

​↱k15,16,19,20,1​,2,3,4,5,7,10⇓−, −, −, −,1​,2,3,4,5,7,10,15,16,19,20​target:5target:5​