当前位置：首页 > article >正文

【笑着写算法系列】二分查找

article 2025/1/31 22:35:18

前言

一、在排序数组中查找元素的第一个和最后一个位置

二、搜索插入位置

三、山脉数组的封顶索引

四、寻找峰值

五、寻找旋转排序数组中的最小值

前言

这篇文章已然来到二分查找的题目，二分查找相信大家很多都听过，学校也常教，但是二分远不止学校教的那种形式简单，二分代码看着简单，但对于有些题目思想还是复杂，且细节多很容易发生死循环。

了解二分的两套使用模板：

求最左端点：

 int left=0,right=nums.length-1;
 int mid;

while(left<right){
         mid=(right-left)/2+left;
        if(nums[mid]<target) left=mid+1;
        else right=mid;
  }

如果我们将target值设为6那么，那么left和right最后的指的下标是最靠左的6

求最右端点：

int left=0,right=nums.length-1;
int mid;
while(left<right){
         mid=(right-left+1)/2+left;
         if(nums[mid]<=target) left=mid;
         else right=mid-1;
 }

这里left和right指的会是最右边的最后一个6的下标。

一、在排序数组中查找元素的第一个和最后一个位置

题目解析：在一个非递减的数组中，找出最左边的target和最右边的tagret下标。也就是说target有可能是有多个的。

参考代码及其解析：

我们先创建好要返回的数组，储存上两个-1。

然后开始进行二分查找（最左端二分查找）。

最左端得二分查找中左后在left==right时结束循环，如果存在结果则这个结果一定是最左边的。

而且在其中有3个小细节：

mid=(right-left)/2+left;在求最左端的target时，mid的求值必须是这个。
结束条件必须是left<right,不能有等号。
在没结束前的循环中[lefft,mid]这段子数组中，永远都没有target。所以left总是要跳出这段区间left=mid+1而我们的right=mid，因为他不能跳出[mid,right]的区间中，结果可能存在这段区间中，如果没有则代表整段数组中都没有target。

循环结束后我们直接判断target即可，如果相等代表找到最左端的target，后面就直接往后找最右端即可

最右端的查找方式与左端相似，不同的只要是right=mid-1；left=mid；以及mid=(right-left+1)/2+left;

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] arr={-1,-1};

        if(nums.length==0) return arr;


        int left=0,right=nums.length-1;
        int mid;

        while(left<right){
            mid=(right-left)/2+left;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }



        if(nums[left]==target){
            arr[0]=left;
            arr[1]=right;
        }else return arr;

        left=0;right=nums.length-1;

        while(left<right){
            mid=(right-left+1)/2+left;
            if(nums[mid]<=target) left=mid;
            else right=mid-1;
        }

        if(nums[right]==target){
            arr[1]=right;
        }



        return arr;

    }
}

注意数组里没有元素的情况。

二、搜索插入位置

题目解析：很简单就是在一个升序数组中找到一个位置下标插入target后还是一个升序数组。

代码及其解析：这里我们直接使用求最左端点的二分查找即可，注意的是如果数组中全都比target小，我们此时需要做特殊处理因为这样我们查到的下标是数组最后一个，但我们需要返回的是下一位。如：1，2，3，4.target=5

此时我们需要插入下标4的位置，但我们的二分是查不到那里的。

class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums[0]>target) return 0;
        if(nums[nums.length-1]<target) return nums.length;


        int left=0,right=nums.length-1,mid;
        while(left<right){           
            mid=(right-left)/2+left;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }


        return right;
    }
}

三、山脉数组的封顶索引

题目解析：就是在一个峰值数组中找到那个最大的值的下标。

参考答案及其解析：

这道题这么一看好像不太符合二分的使用条件啊，毕竟在我们平时认识得二分都是要说在递增或递减的情况下使用二分算法，但其实二分的使用条件是有二段性即可。即left和right所在的那段区间的值都有不同的性质。

这道题我们使用一个普通的求右端点的代码，直接返回结果即可。

class Solution {
    public int searchInsert(int[] nums, int target) {
     
        if(nums[nums.length-1]<target) return nums.length;


        int left=0,right=nums.length-1,mid;
        while(left<right){           
            mid=(right-left)/2+left;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }


        return right;
    }
}

四、寻找峰值

题目解析：在一个数组中，这个数组中元素的大小可能是一条波浪线的即存在多个峰值，那么这时我们返回其中一个即可。

代码及其解析：

首先我们判断这个数组是否有二段性呢，其实也是有的，left所在的位置永远都可以在递增区间，right永远在递减区间，这就是二段性

那么还是套用一个简单的二分模板即可

class Solution1 {
    public int findPeakElement(int[] nums) {
        int left=0,right=nums.length-1,mid;
        while(left<right){
            mid=(right-left+1)/2+left;
            if(nums[mid-1]<=nums[mid]) left=mid;
            else right=mid-1;
        }
        return right;
    }
}

五、寻找旋转排序数组中的最小值

代码及其解析：

首先我们看题目我们要返回的是翻转的数组中最小的那个值，那么我们可以看到例子中，在分割的两个数，5，1以及第二题的7，0无论哪一题都是返回第二个值，那么我们这时就可以使用二分，且用求最左端点的方式更加简便，及如下代码：

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

        return nums[left];
    }
}

查看全文

http://www.kler.cn/a/526443.html