【算法】【算法杂谈】旋转数组的二分法查找-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】【算法杂谈】旋转数组的二分法查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个从小到大有序的数组，该数组存在重复的数，并且该数组可能经过旋转处理，如arr = [1,2,3,4,5,6,7]代表数组未旋转，如果arr=[4,5,6,7,1,2,3],则表示该数组被旋转了，求该数组中的最小值

解决方案

原问题：
首先有一个规律，如果该数组没有被旋转，那么arr[0] 一定小于arr[n-1],否则一定是旋转过的
【算法】【算法杂谈】旋转数组的二分法查找
没有重复的情况如上
=
当l = mid = r相同时：

比较极端的情况，但是仍然是递增数组
【算法】【算法杂谈】旋转数组的二分法查找

具体代码请看代码逻辑处理

代码编写

java语言版本

原问题：
方法一：



    /**
     * 二轮测试：旋转数组的二分法查找
     * @param arr
     * @return
     */
    public static int getMinCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int low = 0;
        int mid = 0;
        int high = arr.length - 1;
        while (low < high) {
            if (low == high - 1) {
                break;
            }
            if (arr[low] < arr[high]) {
                return arr[low];
            }
            mid = (low + high) / 2;
            if (arr[low] > arr[mid]) {
                high = low;
                continue;
            }
            if (arr[low] < arr[mid]) {
                low = mid;
                continue;
            }
            while (low < mid) {
                if (arr[low] < arr[mid]) {
                    return arr[low];
                }else if (arr[low] == arr[mid]) {
                    low++;
                    continue;
                }else {
                    high = mid;
                    break;
                }
            }
        }
        return Math.min(arr[low], arr[high]);
    }


    public static void main(String[] args) {
        System.out.println(getMinCp1(new int[] {1,2,3,4,5}));
    }