点击上方蓝字设为星标

下面开始今天的学习～

今天分享的题目来源于 LeetCode 上第 153 号问题：寻找旋转排序数组中的最小值。也是《剑指Offer》上的一道经典题。

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组  [0，1，2，4，5，6，7] 可能变为 [4，5，6，7，0，1，2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

   

    

     

      

     
     

      

       输入: [
       3，
       4，
       5，
       1，
       2]
      
     
    

     

      

     
     

      

       输出: 
       1
      
     
   

示例 2:

   

    

     

      

     
     

      

       输入: [
       4，
       5，
       6，
       7，
       0，
       1，
       2]
      
     
    

     

      

     
     

      

       输出: 
       0
      
     
   

题目解析

这道题目最简单粗暴的方式就是 直接遍历 整个数组来寻找，这个方法的时间复杂度为 O(N)，空间复杂度为 O(1) 。

不过，这样来做的话完全没有利用到题目给出一个条件 旋转 。

事实上，可以考虑将时间复杂度从 O(n) 缩小到 O(lgn)，这时候 二分查找法 就浮现在脑海。

当然，这里是 二分查找法 的一种变体。

更多有关二分查找法的文章点击这篇：一网打尽！二分查找解题模版与题型全面解析

二分的方法可以保证每次比较后，去掉数组中一半的元素。

这道题目中可以将 中点 与 终点 进行比较。

• mid < end：最小值在左半部分。

• mid > end：最小值在右半部分。

也就是说只需要把 mid 和 end 比较，mid < end 丢弃右半部分（更新 end = mid），mid > end 丢弃左半部分（ 更新 start = mid + 1）。

直到 end 等于 start 时候结束就可以了。

补充：之所以这里 更新 start = mid + 1 而不是 start = mid 是因为存在一种特殊情况。当数组只剩两个元素的时候，mid = （start + end）/ 2，mid 取的就是 start。然后如果此时 mid > end，会发现 start 的位置不会变化，出现 死循环。（可以通过以下动画加深理解）

动画描述

代码实现

   

    

     

      

     
     

      

       //author:程序员吴师兄
      
     
    

     

      

     
     

      

       //source:图解面试算法
      
     
    

     

      

     
     

      

       class Solution {
      
     
    

     

      

     
     

      

           public 
       int findMin(
       int[] nums) {
      
     
    

     

      

     
     

      

               
       int low = 
       0, high = nums.length - 
       1;
      
     
    

     

      

     
     

      

               while (low < high) {
      
     
    

     

      

     
     

      

                   
       if (nums[low] < nums[high]) 
       return nums[low];
      
     
    

     

      

     
     

      

                   
       int mid = low + (high - low) / 
       2;
      
     
    

     

      

     
     

      

                   
       if (nums[mid] > nums[high]){
      
     
    

     

      

     
     

      

                      low = mid + 
       1; 
      
     
    

     

      

     
     

      

                   } 
       else{
      
     
    

     

      

     
     

      

                      high = mid;
      
     
    

     

      

     
     

      

                   } 
      
     
    

     

      

     
     

      

                 }
      
     
    

     

      

     
     

      

               
       return nums[low];
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       }
      
     
   

复杂度分析

• 时间复杂度：和二分搜索一样 O(logN)

• 空间复杂度：O(1)

相关题目推荐

• LeetCode 33：搜索旋转排序数组

• LeetCode 154：寻找旋转排序数组中的最小值 II