面试题 10.03. 搜索旋转数组(二分+存在重复元素的旋转数组)

面试题 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 （没有找到）

提示:

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

 1 class Solution {
 2 public:
 3     int search(vector<int>& arr, int target) {
 4         int left = 0;
 5         int right = arr.size() - 1;
 6         while (left <= right) {
 7             int mid = left + (right - left) / 2;
 8             // 如果左侧与目标值相同,直接返回左侧索引位置
 9             if (arr[left] == target) {
10                 return left;
11             }
12             // 如果中间与左侧相同,但最左侧不为目标值,需过滤最左侧
13             if (arr[left] == arr[mid]) {
14                 left++;
15                 continue;
16             }
17             // 如果中间位置与目标值相同,则看左边是否存在与目标值相同的
18             if (arr[mid] == target) {
19                 right = mid;
20             } else if (arr[left] < arr[mid]) { // 左侧是升序,查找目标值是否在左侧
21                 if (target >= arr[left] && target < arr[mid]) {
22                     // 目标值在左侧
23                     right = mid - 1;
24                 } else {
25                     // 目标值在右侧
26                     left = mid + 1;
27                 }
28             } else {
29                 // 右边是升序,查找目标值是否在右侧
30                 if (target > arr[mid] && target <= arr[right]) {
31                     // 目标值在右侧
32                     left = mid + 1;
33                 } else {
34                     // 目标值在左侧
35                     right = mid - 1;
36                 }
37             }
38         }
39         return -1;
40     }
41 };