二分法查找

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

整理了一下最近三天的力扣题，都是和二分法相关的。
首先我们应知道，使用二分法的前提就是数组有序，但是这三题都是将一个原本非降序的数组旋转后得到一个两部分都有序的数组，增加了点难度。
我们一个一个来看：

题解给了一张图，我觉得很便于理解，旋转后的数组是这样

我们要想找最小值，我们可以先取一个low代表左端点，一个high代表右端点，然后mid=low+high/2，如果nums[mid]<nums[high]，说明最小值在mid或者mid左边，我们可以舍弃右半段，如果nums[mid]>nums[high]，说明最小值在mid右边，我们可以舍弃左半段，当low==high时，我们就退出，此时nums[low]对应的就是最小值，因为不存在重复元素，所以不存在nums[mid]==nums[high]的情况，时间复杂度是O(logn)，空间复杂度O(1)。
具体代码如下:

class Solution {
    public int findMin(int[] nums) {
        int low=0,high=nums.length-1;
        while(low<high){
            int mid=(low+high)/2;
            if(nums[mid]<nums[high]){
                high=mid;
            }else{
                low=mid+1;
            }
        }
        return nums[low];

    }
}

再看第二题：

这一题和上一题有一点不同，就是数组里可以有重复元素了，所以就多了一种情况nums[mid]==nums[high]，题解又给了一张图，很便于理解

图中的pivot就是mid的意思，当nums[mid]==nums[high]时，我们无法确定最小值在左半段还是右半段，但是我们可以确定最右边的边界可以去掉，因为至少mid的值和他一样小，所以就可以将右边界-1，平均时间复杂度是O(logn)，最坏时间复杂度O(n)，空间复杂度O(1)。
代码如下:

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

    }
}

来看最后一题

这题和前两题不太一样，他可以有重复元素，而且他不是找最小值，而是找是否存在目标值，虽然这题用了二分查找，但是因为不知道旋转后的具体位置，所以无法做到真正的二分查找，只能做到局部的二分查找，最坏情况下时间复杂度是O(n)，空间复杂度O(1)。
这一题还可以用上一题的图

当我们用二分法查找时
有三种情况：
第一种nums[left]==nums[mid]==nums[right]，这个时候无法判断目标值在哪半段，但是可知left和right已经不是目标值（自己判断，如果是就返回true结束了），所以左右端点可以同时缩进1
第二种nums[left]<=nums[mid],可知左半段有序，如果目标值在左半段，就在左半段搜索，否则在右半段搜索
第三种nums[left]>nums[mid] (其实等同于nums[mid]<=nums[right]，即右半段有序)，如果目标值在右半段，就在右半段搜索，否则在左半段搜索
代码如下：

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {//左=中=右
                ++l;
                --r;
            } else if (nums[l] <= nums[mid]) {//左半段有序
                if (nums[l] <= target && target <= nums[mid]) {
                    r = mid ;
                } else {
                    l = mid + 1;
                }
            } else {//nums[l]>nums[mid] 右半段有序
                if (nums[mid] <= target && target <= nums[r]) {
                    l = mid ;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;

    }
}

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