首页 > 编程语言 >算法总结-二分查找(两种模板方法总结)

算法总结-二分查找(两种模板方法总结)

时间:2022-12-11 14:23:09浏览次数:45  
标签:总结 二分 right int mid 取整 区间 模板 left

【二分查找】

定义:

二分查找也称折半查找(Binary Search),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也可以是数组中某一区间的起始位置和终止位置。

前言:

二分查找的思路不难理解,但是里面有许多细节问题需要注意,比如边界条件,循环结束条件中 left 和 right 的关系,更新 left 和 right 位置时要不要加 1 减 1。下面的三种模板,是从其他博客整理到的,但是实际上掌握一种就行,主要需要注意细节问题,不管哪种模板一定要判断的是 下一轮「向左找」还是「向右找」,还有 mid 是不是有可能是问题的答案,这一点应该从题目中分析得到,所以一定要认真审题~

二分查找法两种模板写法:

模板一:

while (left <= right) ,这种写法里面的 left 和 right 都要加 1 或者减 1,还要判断 mid 位置的值有可能是解的时候,把 mid 的值保存下来,退出循环以后 left 在右,right 在左,即left == right + 1,写成区间 [left..right] ==> [right+1, right]为空区间,表示没找到,直接返回-1即可;

 1 class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1; 
 4         while(left <= right) { // 注意
 5             int mid = left + (right - left) / 2; 
 6             if(nums[mid] == target) {   
7 return mid; 8 } else if(nums[mid] < target) { 9 left = mid + 1; // 注意 10 } else { 11 right = mid - 1; // 注意 12 } 13 } 14 // 相关返回值 15 return -1; 16 } 17 }

模板二:

while (left < right) ,这种写法的好处是在循环结束的时候不用判断应该返回left还是right。因为循环结束的条件是 left ==  right,区间 [left..right] 有 1 个元素,如果可以确定区间[left, right]一定有解,直接返回left即可,否则需要对left这个位置的元素单独判断一次。

搜索区间[left, right]是配对形式存在的:

  • 要么是[left, mid-1]和[mid, right]即left = mid 与 right = mid - 1,mid需要向上取整:mid = left + (right - left) / 2 ;
  • 要么是[left, mid]和[mid+1, right]即left = mid + 1 与 right = mid ;

小提醒:在写相关逻辑语句的时候,可以在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是 [mid..right] ,这个时候就设置 left = mid,这种情况的反面区间就是 [left..mid - 1] ,那么 else 就设置 right = mid - 1,所以就不用记忆配对关系了。

 1  class Solution {
 2      public int searchInsert(int[] nums, int target) {
 3          int left = 0, right = nums.length - 1; 
 4          while(left < right) { // 注意
 5             int mid = (left + right) / 2; // 注意
 6             if(nums[mid] <= target) {
 7                // 相关逻辑
 8                left = mid + 1
 9             } else {
10                right = mid; // 注意
11             }
12          }
13          // 相关返回值
14         return nums[left] == target ? left : -1;
15     }
16  }

 【向上取整】与【向下取整】

向上取整与向下取整主要是为了处理当只剩下两个元素的情况,这时 left 和 right 相差1。

向上取整:把整个区间划分成[left, mid -1] 和 [mid, right],把mid划分给了右区间,如果操作是选择了包含mid的这个区间,那么就需要mid值来更新left,如果向下取整,left和right值算出来的mid就与left相等(例如:(4+5) / 2 == 4),再将left更新成mid,相当于没有更新left,故需要向上取整,算出来的mid值与right相等,这样left向右移动,得到更新,和right指向相同的值。

向下取整:把整个区间划分成[left, mid] 和 [mid + 1, right],把mid划分给了左区间,如果操作是选择了包含mid的这个区间,那么就需要mid值来更新right,如果向上取整,left和right值算出来的mid就与right相等(例如:(5 + 4) / 2 +1 == 5),再将right更新成mid,相当于没有更新right,故需要向下取整,算出来的mid值与left相等,这样right向左移动,得到更新,和left指向相同的值。

总结:

mid如果被分给了右区间,需要向上取整,保证left能够被新值更新。

mid如果被分给了左区间,需要向上取整,保证left能够被新值更新。

标签:总结,二分,right,int,mid,取整,区间,模板,left
From: https://www.cnblogs.com/liu-myu/p/16889741.html

相关文章

  • 2022-2023-1 20221301 《计算机基础与程序设计》第十五周学习总结
    2022-2023-120221301《计算机基础与程序设计》第十五周学习总结作业信息这个作业属于哪个课程<班级的链接>https://edu.cnblogs.com/campus/besti/2022-2023-1-CFA......
  • 总结2017 展望2018
    LZ-Says:时间过得真快,又是一年过去了,不知道大家这一年收获了什么,失去了什么,对未来又有什么样的计划?这里,且听LZ短暂述说~过去的20172016年12月31号~2017年1月1号,好兄弟聚集一......
  • P5410 【模板】扩展 KMP(Z 函数)
    题目链接P5410【模板】扩展KMP(Z函数)【模板】扩展KMP(Z函数)题目描述给定两个字符串\(a,b\),你要求出两个数组:\(b\)的\(z\)函数数组\(z\),即\(b\)与\(b\)的......
  • C++:类模板知识回顾
    概述类的私有、公有、类继承有时并不能满足我们的开发需求,尤其是将类作为容器(泛型编程)使用时,因此类模板在C++随之衍生。相关概念也会在下文中一一阐述~模板类的定义与使......
  • 学期 2022-2023-1 学号:20221425 《计算机基础与程序设计》第十五周学习总结
    学期(如2022-2023-1)学号(如:20221425)《计算机基础与程序设计》第十五周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2022-2023-1-计算机基础与程序设计)......
  • Java 线程池之Jetty 线程池学习总结
    Java线程池之Jetty线程池学习总结前提Jetty11.0.x为什么是Jetty?Java提供4中创建线程池的快捷方式Executors.newFixedThreadPool();Executors.newCachedThreadPool();Exe......
  • 模板链表类的扩展(QListEx<T>)
    以前写的链表都是比较简单的,插入节点是在头节点上,所以循环链表时都是从最后一个数据往前找的,给人的感觉是倒着的,今天写一个在链表尾部插入数据1。链表节点类的定义/链......
  • 2022-2023-1 20221307张城玮 《计算机基础与程序设计》 第十五周学习总结
    作业信息班级链接:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK15作业链接:2022-2023-120221307......
  • 把时间沉淀下来 | Kagol 的 2022 年终总结
    现代管理学之父德鲁克在其经典著作《卓有成效的管理者》中对时间有一段精妙的论述,其要点如下:时间是一项限制因素,任何生产程序的产出量,都会受到最稀有资源的制约,而时间就......
  • 我们常用于猜数字游戏的二分查找算法怎么用python实现呢?
    原理简单介绍类比猜数游戏我们上篇文章唠了唠经典的冒泡排序算法,如果说经典算法,那怎么少得了二分查找呢.可以说它是经典中的经典,就我们常用于猜数字方法.就是他.比如猜1......