搜索旋转数组

题目链接

搜索旋转数组

题目描述

注意点

• 数组已被旋转过很多次
• 数组元素原先是按升序排列的
• 若有多个相同元素，返回索引值最小的一个

解答思路

• 首先需要知道的是，本题数组中的旋转多次只是将头部的某些元素移动到尾部，所以不论怎么旋转，数组都是有一定顺序的，最差的情况是分为两段递增的子数组
• 因为数组是有一定顺序的，所以首先考虑二分查找搜索数组，本题数组可能是两段递增的子数组组成并且数组中的元素可能重复，所以要考虑多方面：
  • 如果二分后的左区间是严格递增的：如果target在arr[left]~arr[mid]之间，说明target就在左区间内（不在左区间说明不存在），继续向左二分；否则说明target在右区间内，向右二分
  • 如果二分后的左区间是由两段递增的子数组组成的：如果target >= arr[left]或target <= arr[mid]，说明target就在左区间内，继续向左二分；否则说明target在右区间内，向右二分
  • 如果二分后的左区间内的值都是相同的（arr[left] = arr[mid]）：如果此时target等于该值，则直接将右边界移动到左边界即可（此时left就是结果值）；否则需要不断移动左边界（每次移动一格，清除重复值）找到target

代码

class Solution {
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            // 左区间升序
            if (arr[left] < arr[mid]) {
                // 值在左区间内
                if (target >= arr[left] && target <= arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
                continue;
            }
            // 左区间不升序
            if (arr[left] > arr[mid]) {
                // 值在左区间内
                if (target >= arr[left] || target <= arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
                continue;
            }
            // 左区间值都相同 
            if (arr[left] == arr[mid]) {
                // 注意清理重复值
                if (arr[left] != target) {
                    left++;
                } else {
                    right = left;
                }
            }
        }
        return arr[left] == target ? left : -1;
    }
}

关键点

• 二分查找的思想
• 注意边界问题
• 注意有多个重复的target时怎么找到最小的索引