leetcode：面试题 10.03. 搜索旋转数组

题目

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

示例：

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

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

本题与 [中等] 33. 搜索旋转排序数组 的区别在于，数组中可能存在重复数字

解答 & 代码

参考：https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/xuan-zhuan-shu-zu-cong-yi-dao-nan-ge-ge-dcv7a/

二分查找

class Solution {
public:
    int search(vector<int>& arr, int target) {       
        int left = 0;
        int right = arr.size() - 1;
        while(left <= right)
        {
            // 重点 1：当左边界 left == target 时直接返回，因为找的就是 target 的最小索引
            if(arr[left] == target)
                return left;

            int mid = left + (right - left) / 2;
            // 重点 2：当中间值 mid == target 时，右边界 right 收缩到 mid
            // 因为左边可能还存在 target（只是可能，所以是收缩到 mid 而不是 mid-1）
            if(arr[mid] == target)
                right = mid;
            // 如果 mid 处于旋转数组旋转点左侧，则当前左半部分 [left, mid] 有序
            // 注意是小于号，等于要单独处理（若arr[mid]等于arr[0]，无法判断 mid 处于旋转点左侧还是右侧）
            else if(arr[0] < arr[mid])
            {
                // 如果 target 处于有序的左半部分，则右边界收缩
                if(arr[left] <= target && target < arr[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 如果 mid 处于旋转数组旋转点右侧，则当前右半部分 [mid, right] 有序
            else if(arr[0] > arr[mid])
            {
                if(arr[mid] < target && target <= arr[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            // 重点 3：如果 arr[0] == arr[mid]，则无法判定 mid 处于旋转点左侧还是右侧
            // 当前唯一可以确定的是 arr[left] != target（while 循环最开始判断）
            // 因此，令 left 右移
            else if(arr[0] == arr[mid])
                ++left;
        }
        return -1;
    }
};

复杂度分析：设数组长为 N

• 时间复杂度 O(log N)：
• 空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 84.45% 的用户
内存消耗：11.9 MB, 在所有 C++ 提交中击败了 87.75% 的用户