看“旋转数组”中的二分查找笔记与实践

梦里梦外; 2022-01-22 03:49 217阅读 0赞

周一看了程序员小灰推送的一篇旋转数组中的二分查找，当时看着有点懵懂懵懂的，就像这自己来实现一下，原谅一拖再拖，昨天晚上来实现了，的确开始有点烧脑，但是明白了也就那么回事。[你可点击此处查看原文查看。][Link 1]

于是就记录下来，算是学习分享笔记吧。

首先得知道旋转数组是什么？上面文章链接中讲的很清楚。如：

![0_wx_fmt_png][]

在一个升序或者降序数组中，把原来第一个位置到以后的n个位置拿到后面去了，这就是旋转数组，（看图就知道了）。

查找分析：

根据程序员小灰大佬文章发现

查找关键在于中间的数与旋转点（即原数组第一个数）之间的位置关系。

23,40,43,50,59,63,66,68,88,89,90,99,100,2,4,6,9,10,15,17

我们试着推一下：

/**
     *  判断中位数 在旋转点左边还是右边，
     *    如何判断旋转点在中位数左边还是右边呢？？
     *    在升序数组下，中位数大于第一个数，表明*旋转点*在中位数右边，则中位数左边升序，
     *    如 ：5,7,8,9,10,11,2,3,4   2 是旋转点，中位数是 10
     *
     *    中位数小于第一个数，表明*旋转点*在中位数左边，则中位数右边升序
     *    9,10,11,2,3,4,5,7,8,  2 是旋转点，中位数是 3
     *
     */

（这里不用刻意去看旋转点在何处，而是根据数组第一个数来判断中位数与旋转点的位置关系）

中位数与旋转点的位置关系确定了，然后就可以回归到普通升序或降序数组的中位数与要查找数的位置关系了。

完整代码如下:

private static int rotatedBinarySearch(int[] array2, int target) {
    
        int start  = 0, end = array2.length-1;  //获得第一个下标，最后一个下标
        int mid; //获得中位数
        while (start <= end){
    
            mid  = start + (end - start)/2;
            //判断要查找的数是否等于中位数
            if(target== array2[mid]){
                return mid;
            }
            /**
             *  判断中位数 在旋转点左边还是右边，
             *    如何判断旋转点在中位数左边还是右边呢？？
             *    在升序数组下，中位数大于第一个数，表明*旋转点*在中位数右边，则中位数左边升序，
             *    如 ：5,7,8,9,10,11,2,3,4   2 是旋转点，中位数是 10
             *
             *    中位数小于第一个数，表明*旋转点*在中位数左边，则中位数右边升序
             *    9,10,11,2,3,4,5,7,8,  2 是旋转点，中位数是 3
             *
             */
            if(array2[mid] <= array2[start]){  //中位数小于第一个数，旋转点在中位左边
                //判断查找的数是否小于最右侧，大于中位数
                if(array2[mid]< target && target <=array2[end]){
                    //满足，说明查找数在中位数在右边
                    start = mid +1;
                }else{
                    end = mid - 1;
                }
            } else {  //中位数大于第一个数，旋转点在中位右边
                //判断查找的数是否大于最左侧，小于中位数
                if(array2[mid]> target && target >=array2[start]){
                    //满足，说明查找数在中位数在左边
                    end = mid - 1;
                }else{
                    start = mid +1;
                }
            }
        }
        return -1;
    }

[Link 1]: https://mp.weixin.qq.com/s/33aOwDGFQ5omE3sHmVLXVA
[0_wx_fmt_png]: /images/20220122/b1d7c42589fa45fca172c4871e295a0d.png