题解 | #牛牛的旋转搜索#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 如果中间元素等于目标
            if (arr[mid] == target) {
                // 继续向左搜索最小的索引
                while (mid > 0 && arr[mid - 1] == target) {
                    mid--;
                }
                return mid;
            }

            // 如果中间元素大于左边界元素，说明左半部分是有序的
            if (arr[mid] > arr[left]) {
                // 如果目标在左半部分有序数组中，更新右边界为 mid - 1
                if (target >= arr[left] && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    // 否则更新左边界为 mid + 1
                    left = mid + 1;
                }
            } else if (arr[mid] <
                       arr[left]) { // 如果中间元素小于左边界元素，说明右半部分是有序的
                // 如果目标在右半部分有序数组中，更新左边界为 mid + 1
                if (target > arr[mid] && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    // 否则更新右边界为 mid - 1
                    right = mid - 1;
                }
            } else { // 如果中间元素等于左边界元素，无法判断哪一部分是有序的
                // 缩小搜索范围，去掉左边界元素
                left++;
            }
        }

        return -1; // 没有找到目标元素
    }
}

本题知识点分析：

1.二分查找

2.数组遍历

3.数学模拟

本题解题思路分析：

1.如果中间元素等于目标，继续向左搜索最小的索引

2.如果中间元素大于左边界元素，说明左半部分是有序的

3.如果中间元素小于左边界元素，说明右半部分是有序的

4.然后就是分别判断目标是在左半区域还是右半区域

5.如果没有找到目标数组就返回-1

本题属于纯数学模拟+一点二分查找，你要跟别人解释其实也就那样，看了题解就恍然大悟，属于背题类

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~