leetcode 153、154. 寻找旋转排序数组中的最小值【二分查找：利用有序的一半缩小范围】

旧城等待， 2022-11-17 13:34 132阅读 0赞

思路和[leetcode 33. 搜索旋转排序数组][leetcode 33.]  
一样

class Solution { 
    public:
        int findMin(vector<int>& a) { 
            int n = a.size();
            int l =0;
            int r = n-1;
            int ret = INT_MAX;
            while(l<=r){ 
                int m = (l+r)>>1;
                if( a[l] <= a[m] ){ 
                    ret = min(ret,a[l]);
                    l = m+1;
                }else if(a[m]<=a[r]){ 
                    ret = min(ret,a[m]);
                    r = m-1;
                }
            }
            return ret;
        }
    };

![在这里插入图片描述][20210409142247938.png]

有重复元素就需要额外考虑  
如果数组最后一个元素和第一个元素一样的话，就把后面的删掉

class Solution { 
    public:
        int findMin(vector<int>& a) { 
            int n = a.size();
            int l =0;
            int r = n-1;
    
            int ret = INT_MAX;
            //如果数组最后一个元素和第一个元素一样的话，就把后面的删掉
            while(r>=0 && a[r]>=a[l]){ 
                ret = min(ret,a[r]);
                --r;
            }
            
            while(l<=r){ 
                int m = (l+r)>>1;
                if( a[l] <= a[m] ){ 
                    ret = min(ret,a[l]);
                    l = m+1;
                }else if(a[m]<=a[r]){ 
                    ret = min(ret,a[m]);
                    r = m-1;
                }
            }
            return ret;
        }
    };

![在这里插入图片描述][20210409142207589.png]

[leetcode 33.]: https://liyunhao.blog.csdn.net/article/details/115487763
[20210409142247938.png]: /images/20221022/5a71b5cadd4c4f5b8b02e30427ecd1a0.png
[20210409142207589.png]: /images/20221022/905ca5de72914b5ab11345b8a1ce4c80.png