忙着追剧的村长头像
LeetCode刷题二分查找(二分查找+在排序数组中寻找元素的第一个和最后一个位置)Java封面图

LeetCode刷题二分查找(二分查找+在排序数组中寻找元素的第一个和最后一个位置)Java

总结朴素二分查找的模版

朴素二分查找是一种在有序数组中查找目标元素的算法。它每次比较中间元素,根据比较结果排除一半不可能存在目标值的区间,从而不断缩小查找范围。

  • 前提条件: 数组必须有序(通常为升序)。

  • 核心思想: 每次取中间值,将查找范围缩小一半。

  • 时间复杂度: \(O(\log n)\)。

  • 空间复杂度: \(O(1)\)。

  • 返回结果: 找到目标值就返回下标,否则返回 -1

一,二分查找

题目解析:

简单的方式当然就是全部遍历一遍然后找到那个目标值,对于二分查找的话就是先将数组排序,然后我们先通过左右下标的形式找到中间的那一个数,然后让这个数和我们的目标值作比较,如果大了那么左边的所有区间肯定就都小了,就可以直接去除一半的空间,大了也是一样的原理,知道找到那个目标值为止

代码演示:

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

二,在排序数组中寻找元素的第一个和最后一个位置

题目解析:

针对这道题目我们需要的是根据左端点以及右端点进行分类讨论,并且还需要注意的是求中点的方式以及循环条件

代码演示:

    public int[] searchRange(int[] nums, int target) {
        int[]ret=new int[2];
        ret[0]=ret[1]=-1;
        if (nums.length==0){
            return ret;
        }
        //先找左端点
        int left=0;
        int right=nums.length-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (nums[mid]>=target){
                right=mid;
            } else{
                left=mid+1;
            }
        }
        if (nums[left]!=target){
            return ret;
        }else{
            ret[0]=left;
        }
        //先找右端点
        left=0;
        right=nums.length-1;
        while (left<right){
            int mid=left+(right-left+1)/2;
            if (nums[mid]<=target){
                left=mid;
            } else{
                right=mid-1;
            }
        }
        ret[1]=right;
        return ret;
    }

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/java_nnnn/article/details/168967590

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--