面试题 10.03.搜索旋转数组

1. 题目描述

搜索旋转数组。给定一个排序后的数组，包含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]之间

标签 数组 二分查找

2. 解题

1. 暴力搜索，时间复杂度O(n)

2. 二分查找

• 左 == target： 直接返回 左
• 左 == 中： 此时target可能在[左，mid]中，也可能在[mid + 1, r]中，左 = 左 + 1
• 左 < 中： 此时需要分情况讨论：
  • target比左小或者target比中大时（比小的都小或者比大的都大）：此时target只可能在[mid, r]中，所以l = mid;
  • 其他，即target比左大并且target比中小时（大小在左和中之间）：此时target只可能在[左 + 1, mid]中，所以 l = l + 1; r = mid;
• 左 > 中： 此时需要分情况讨论：
  • target比左小并且target比中大时（大小在左和中之间）：此时target只可能在[mid, r]中，所以l = mid;
  • 其他，即target比左大或者比中小时（比大的都大或者比小的都小）：此时target只可能在[左 + 1, mid]中，所以 l = l + 1; r = mid;

二分法的总体思路是，先判断mid落在了哪一段上，然后再根据target与arr[l]与arr[mid]的关系确定target应在左边还是右边，从而继续下一次寻找。