二分(折半查找)详细解答(边界条件终止条件等等详细解释)

这篇具有很好参考价值的文章主要介绍了二分(折半查找)详细解答(边界条件终止条件等等详细解释)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

刷 Leetcode 总能遇到关于二分的题目,但是之前也只是草草地了解一下,每次在使用的时候都需要找模板,要不然就需要对于边界条件进行调试,着实是很麻烦!!!


二分介绍:

首先来简单介绍一下二分:二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求 线性表 必须采用 顺序存储结构,而且表中元素按关键字有序排列

优点:

  1. 比较次数少:二分查找每次将搜索范围缩小一半,因此比较次数较少,查找速度快。
  2. 时间复杂度低:在有序数组中,二分查找的时间复杂度为O(log n),其中n为搜索范围的大小。相比线性查找的O(n)时间复杂度,二分查找更高效。
  3. 可靠性高:由于二分查找是基于有序数组进行的,因此在数组有序的前提下,可以保证查找结果的准确性。

缺点:

  1. 要求有序数组:二分查找要求待查表为有序表,如果数组无序,则需要先进行排序操作,增加了额外的时间复杂度。
  2. 插入删除困难:由于二分查找是基于有序数组进行的,插入和删除操作会破坏数组的有序性,因此在插入和删除元素时需要维护数组的有序性,增加了操作的复杂度。
适用范围以及题型:

  在一段有序序列中寻找指定元素(或者该序列中不存在指定元素,返回小于等于指定元素的最大值)等等


二分法讲解:

arr数组为有序序列
left: 左边界 right:右边界 mid = (left + right) / 2: 中间下标 循环条件: left .. right

上述为二分中的左边界(left),右边界(right),中间元素下标(mid).

二分法分类:

1.闭区间(左边界 left = 0, 右边界 right = arr.size() - 1)(从序列中能够找到对应的元素)

先插入代码:

        // 1 2 3 5 6 8 9 10(有序数组中的元素)
        int left = 0, right = arr.size() - 1;
        int goal = 5;
while(left <= right){ int mid = ( left + right) / 2; if(goal > arr[mid]){ left = mid + 1; }else{ right = mid - 1; } cout << "Left:" << left << " " << "Right:" << right << " " ; } cout << "结果是" << left << endl;

我们直接进行分析(先不要想为什么这样子,先跟着我的思路走):
(1)闭区间初始化:
  left = 0, right = arr.size() - 1,则此时 left 和 right 代表的分别是数组序列的起始元素和末尾元素
(2)循环条件的设置:
  循环结束的标志是区间内没有元素,因此只有当 left < right 的时候才会终止,因此设置 while(left <= right)
(3)循环中 if 语句满足与不满足后的 left 和 right 的设置
  暂时不讨论为什么这样子设置

来看终止情况:
终止前的一次: left == right
设 X = left, Y = right (这里的X和Y是不会变的,因为此时 left == right,所以可以 X == Y)
此时 mid == X (或者Y),结果只有两种可能,goal对应元素下标为 (1)X对应的  或者 (2)X + 1对应的
    前面这句话不理解可以看 while 循环中的 if 语句,流程图如下:
二分(折半查找)详细解答(边界条件终止条件等等详细解释)

 

接着我们分析两种情况:
情况一:X对应的元素是目标值
  则此时进入 if 语句,判断为 N,进入第二个执行语句: right = mid - 1, 则此时 left 不变,结果就是 left, 就是 X

情况二:X + 1对应的元素是目标值
  则此时进入 if 语句,判断为 Y,进入第一个执行语句:left = mid + 1,则此时结果仍然是 left, 就是 X + 1

综上:cout << left << endl; 就可以得到正确答案!

2.闭区间 从序列中寻找小于等于目标值的最大元素

先插入代码:

       // 1 2 3 5 6 8 9 10(有序数组中的元素) 
       bool flag = true;
       int left = 0, right = arr.size() - 1, goal = 11;
       while(left <= right){
           int mid = ( left + right) / 2;
           if(goal > arr[mid]){
               left = mid + 1;
           }else if(goal == arr[mid]){
               cout << "找到相等的元素: "<< mid << endl;
               flag = false;
               break;
           }else{
               right = mid - 1;
           }
        }     
        if(flag) cout << " 小于goal的最大元素下标是" << right << endl; 

 

分析:首先若是区间中出现了与 goal 值相等的元素,则直接返回;
这个是没有问题的,我们考虑如下情况:其中不存在等于 goal 的元素,则进行以下分析:

来看终止情况:
终止前的一次: left == right
设 X = left, Y = right (这里的X和Y是不会变的,因为此时 left == right,所以可以 X == Y)
此时 mid == X (或者Y,因为X == Y),结果只有两种可能,goal对应元素下标为 :(1)X对应的  或者 (2)X - 1对应的
接着我们分析两种情况:(注意:以下情况考虑的时候没有考虑 goal == arr[mid],因为若是出现这种情况则直接结束循环)

情况一:X对应的元素是目标值
  则此时进入 if 语句,判断为 Y,进入第一个执行语句: left = mid + 1, 则此时 right 不变,结果就是 right, 就是 Y (X == Y)

情况二:X - 1对应的元素是目标值
  则此时进入 if 语句,判断为 N,进入第一个执行语句:right = mid - 1,则此时结果是 right, 就是 Y - 1 (Y - 1 == X - 1)

综上:cout << right << endl; 就可以得到正确答案!

 


  

 

 



文章来源地址https://www.toymoban.com/news/detail-746038.html

到了这里,关于二分(折半查找)详细解答(边界条件终止条件等等详细解释)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【二分查找】详细图解

    目录 一.什么是二分查找法? 二.算法要求 三.算法思想 图解(要找的数k的值为3)  参考代码 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序储存结构,而且表中元素按有序排列。  1.必须是 有序排列。

    2024年02月10日
    浏览(81)
  • C++两个矩阵相乘代码(内附有矩阵相乘的条件与规则,以及对代码的详细解答)

         再复制粘贴代码之前可以先了解学习一下什么是矩阵相乘,矩阵相乘的条件与规则又是什么。 点击一下链接即可进入学习:                       #矩阵相乘的学习链接          以下是两个矩阵相乘的代码块(输入版) 补充①:对于for循环了解还不够透彻的可以进

    2024年02月11日
    浏览(41)
  • C语言--顺序查找、折半查找

    顺序查找(sequential search)就是按照 数组 的顺序一 一比较数组中的元素的值和所查找的值。如下图表所示,遍历数组进行比较。若找到,则break跳出循环。 a[0] a[1] a[2] a[3] a[4] 9 12 22 13 34 22==9? 22==12? 22==22?              折半搜索(英语:half-interval search),也称二分搜索、

    2024年02月07日
    浏览(47)
  • 查找:线性表的C语言代码实现(顺序查找、折半查找)

    一、线性表结构 两个类的定义 二、线性表的初始化以及根据输入的元素建立线性表 1.线性表的初始化,初始化一个空的线性表 2.根据用户需求,向线性表中添加元素  三、顺序查找  Search1函数(没有设置哨兵,需要比较两次) 四、顺序查找(设置哨兵,不用再比较是否会越

    2024年02月09日
    浏览(49)
  • C语言——折半查找法

    假如现在有一组数据,你想要查询这个具体某一个数据在这一堆数据中的所在位置,这个时候就需要程序在这一组数据中,找到与想要查找的目标数据相匹配的那个数据,然后返回相对应的位置。如果将问题再细化简化一点,假如现在有一组有顺序的数字,需要你编写程序找

    2024年02月01日
    浏览(37)
  • 折半查找、

    描述 给定一个已按从大到小排序好的数组和一个数,使用折半查找算法,输出该数在数组中的位置。如果该数不在数组中,则输出“无此数”。 输入 输入为两行,第一行包含多个整数,用空格分隔,表示已排序好的数组;第二行为需要查找的数。 输出 输出一个整数,表示

    2024年02月14日
    浏览(72)
  • 折半查找的判定树

    二叉判定树是用于描述解决问题的思路,比如可以使用判定树描述N个数的比较过程,是一种对过程的描述。 它也可以用于描述二分查找(即折半查找,以下都作二分查找)的过程。 描述二分查找的二叉判定树,我们也可以叫折半查找判定树, 从这样的判定树,我们可以分析

    2024年02月08日
    浏览(31)
  • 折半查找实验 (数据结构)

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中,折半查找一个

    2024年02月08日
    浏览(84)
  • 折半查找算法(BinarySearch)

            查找算法是一种在数字列表中确定目标元素所在位置的算法。假设给定一个目标元素 11 和一个包含元素 11 的数字列表(例如 10, 11, 12,13,14, 15, 16, 17, 18, 19, 20),然后在该数字列表中找到目标元素的位置。         折半查找算法也叫做对分查找和二分查找。折半

    2024年02月03日
    浏览(40)
  • 17-数据结构-查找-(顺序、折半、分块)

            简介:查找,顾名思义,是我们处理数据时常用的操作之一。大概就是我们从表格中去搜索我们想要的东西,这个表格,就是所谓的查找表(存储数据的表)。而我们怎么设计查找,才可以让计算机更快的去找到筛选我们所需要的信息呢,因此,关于怎么设计查找

    2024年02月09日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包