[每日一道小算法（二十四）] [二分查找]旋转数组的最小数字（剑指offer习题）

ゞ浴缸里的玫瑰 2023-07-04 15:55 18阅读 0赞

前言：  
这是一道二分查找法变形的题型，很有意义，值得学习。

### 题目类型 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。  
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。  
例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。  
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

### 题目解析 ###

这道题，我们可以直接使用暴力方法，直接遍历数组找到最小值即可，这样的话，时间复杂度有点高为O（n）。但是这道题这么出，显然不可能是让我用这种方法来解决这道题，所以我们需要来重新找一个更好的解决办法。  
我们根据题意，可以看出，这个数组在旋转之前是一个递增的数组，所以根据这一特性，我们可以使用二分查找法来解决这道题。具体分析如下：  
我们用高低位和中间的值来进行比较，看处于递增还是递减序列，进行操作缩小范围。我们定义两个指针，第一个指针指向数组开始处，第二指针指向末尾处。

*  处于递增序列，则low指针进行上移。
 *  处于递减：则high指针下移
 *  其余情况：low++缩小范围  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70 1]

### 代码样例 ###

package com.asong.leetcode.minNumberInRotateArray;
    
    /** * 旋转数组中的最小值 * 解决：定义两个指针，分别是指向数组头的low指针，指向数组末尾的high指针。 * 取中间值，判断是否处于第一段递增数组中，如果是的话，low指针进行上移 * 如果不过的话，high指针下移。 */
    public class Solution1 { 
        public int minNumberInRotateArray(int [] array) { 
            if(array == null || array.length < 1)
            { 
                return 0;
            }
            int low = 0 ;
            int high = array.length -1 ;
            int mid = 0;
            while(low < high)
            { 
                if(array[low] < array[high])
                { 
                    return array[low];
                }
                mid = low + (high - low)/2;
                if(array[mid] > array[low])
                { 
                    low = mid + 1;
                }else if(array[mid] < array[high])
                { 
                    high = mid;
                }else { 
                    low++; // 特殊例子，缩小范围
                }
            }
            return array[low];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200212223226426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200212223242168.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5Mzk3MTY1,size_16,color_FFFFFF,t_70