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

力扣Hot100——35.搜索插入的位置(二分查找)

在这里插入图片描述
除暴力循环,更好的办法是二分查找,降低查询次数。

二分查找思想

如果一个问题,待查找的数是一个整数,且知道范围,大概就可以使用二分查找算法。

  1. 设置 left 、 right 与mid 分别标示数组的头、尾以及中间位置
  2. 每次根据 nums[mid] 与 target 之间的大小进行判断,相等直接返回 mid,若 nums[mid] < target 则 left 右移至 mid+1 ;若 nums[mid] > target 则 right 左移至 mid-1
  3. 查找结束,如果没有相等则返回 left,该值为插入位置下标
  4. 循环退出条件为 left > right
public int searchInsert(int[] nums, int target) {
    // 二分查找法
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    return left;
}

还有一种修改的方式为,将 nums[mid] == target 的情况与 nums[mid] == target 放在一起处理。这样做,在两数相等的时候会错过一次输出,但是在下一次循环的时候,left一定会大于 right,并且 left 指向的就是 target。也就是多循环了一次,少了一些判断。

public int searchInsert(int[] nums, int target) {
    // 二分查找法
    int left = 0, right = nums.length - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(nums[mid] < target){
            left = mid + 1;
        }
        else{	//将 nums[mid] < target 放在这里处理
            right = mid - 1;
        }
    }
    return left;
}

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

相关文章:

  • [C语言]数据在内存中的存储
  • ai数字人系统系统saas源码 一站式开发目录
  • 前端 git规范-不同软件(GitHub、Sourcetree、WebStorm)、命令行合并方式下增加 --no-ff的方法
  • 【Vue】上传PDF功能
  • 鸿蒙路由 HMrouter 配置及使用一
  • Android笔记:Android平台下SVG格式的解析与实践
  • PyTorch使用-张量数值计算
  • 每日Attention学习27——Patch-based Graph Reasoning
  • 【从零开始学习计算机科学】软件工程(六)软件质量
  • Docker基础知识介绍
  • 【Python+HTTP接口】POST请求不同请求头构造
  • 【ASMbits--常用算术运算指令】
  • 深入解析 FID:深度学习生成模型评价指标
  • pyQT学习笔记——Qt常用组件与绘图类的使用指南
  • 【商城实战(36)】UniApp性能飞升秘籍:从渲染到编译的深度优化
  • 使用memmove优化插入排序
  • 软件架构设计习题及复习
  • 计算机网络——NAT
  • 【Linux】Socket 编程 TCP
  • 《Python深度学习》第四讲:计算机视觉中的深度学习