排序-二分查找

本文主要是介绍排序-二分查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例题：

• 寻找旋转排序数组中的最小值
  网址：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
  前沿： 下面给出两种解法，分别从两个角度：
• 常规想法，考虑的性质是：序列中最小的数据要么是第一个要么是第一个左边数据大于右边的位置
• 二分查找的方式

方法1：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int tmp = nums[0];
        auto iter = nums.begin();
        nums.insert(iter, *iter-1);    //增加一个开头数
        iter = nums.begin()+1;
        for(;iter!=nums.end();iter++){
            if(*prev(iter,1)>*iter){
                tmp = *iter;
                break;
            }
        }
        return tmp;
    }
};

注意点：采用容器的prev函数获取前一个的地址，所以用迭代器的时候需要考虑增加一个无用的开头新数。

方法2：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int low = 0;
        int high = n-1;
        while(low<high){
            int mid = low + (high - low)/2;
            if(nums[mid]<nums[high])
                high = mid;
            else 
                low = mid+1;
        }
        return nums[low];
    }
};

注意点：这里面二分注意点就是中间元素和最后一个元素的判断关系，如果中间元素小于最后元素，那么mid右边去掉；否则左边去掉。

这篇关于排序-二分查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！