首页 > 编程语言 >课程讲解--深入探究二分算法

课程讲解--深入探究二分算法

时间:2024-11-10 17:45:51浏览次数:3  
标签:二分 -- 元素 mid high 探究 查找 low

 

一、二分查找算法的基本概念

  1. 定义与原理
    • 二分查找,也被称为折半查找,是一种在有序数据集合中查找特定元素的高效算法。其原理基于分治思想,每次查找都将查找区间缩小一半。例如,在一个有序数组中查找一个特定的数字,我们先比较数组中间位置的元素与目标元素的大小。如果中间元素等于目标元素,那么查找成功;如果中间元素大于目标元素,那么目标元素必然在数组的前半部分,我们就将查找区间缩小到数组的前半部分,然后继续在这个新的区间内进行同样的操作;如果中间元素小于目标元素,那么目标元素就在数组的后半部分,我们就将查找区间缩小到后半部分再进行查找。这种不断缩小查找区间的方式使得查找速度非常快。引用自[1]“二分查找是一种非常简单易懂的快速查找算法,生活中到处可见。”
  2. 适用场景
    • 二分查找适用于有序的数据结构,比如有序数组。当数据量较大时,它的优势更加明显。例如,在一个包含大量有序用户信息(按照用户ID或者注册时间等排序)的数据库中查找特定用户的信息,使用二分查找可以快速定位到目标用户。如果数据是无序的,那么首先需要对数据进行排序,然后才能使用二分查找。

二、二分查找算法的实现

  1. 循环实现方式
    • 在C++ 中,一个简单的二分查找函数实现如下:
boolbsearch(std::vector<int>&vec, intvalue) { 
    if (vec.empty())  { 
        returnfalse; 
    } 
    intlow = 0, high = vec.size()  - 1; 
    //当前查找的区间 
    while (low <= high) { 
        intmid = low+((high - low)/2); 
        if (vec[mid]==value) { 
            //找到了 
            returntrue; 
        } else if (vec[mid]>value) { 
            low = mid + 1; 
            //更新要查找的区间 
        } else { 
            high = mid - 1; 
            //更新要查找的区间 
        } 
    } 
    returnfalse; 
} 
  • 这里需要注意几个容易出错的地方:
    • 循环退出条件:循环退出条件是low <= high,而不是low < high。如果写成low < high,可能会导致某些情况下无法正确找到目标元素。引用自[1]“注意是low <= high,而不是low < high”。
    • mid的取值:不能简单地写成mid=(low + high)/2。因为如果lowhigh比较大的话,两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high - low)/2。因为相比除法运算来说,计算机处理位运算要快得多。引用自[1]“不能写成,mid=(low + high)/2。因为如果lowhigh比较大的话,两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high - low)/2”。
    • low和high的更新low = mid+1high = mid - 1。注意这里的+1 - 1,如果直接写成low = mid或者high = mid,就可能会发生死循环。引用自[1]“注意这里的+1 - 1,如果直接写成low = mid或者high = mid,就可能会发生死循环”。
  1. 递归实现方式
    • 除了使用循环来实现二分查找,还可以用递归来实现。以下是一个递归实现二分查找的伪代码示例:
function binarySearchRecursive(array, target, low, high) { 
    if (low > high) { 
        return false; 
    } 
    int mid = low+((high - low)/2); 
    if (array[mid]==target) { 
        return true; 
    } else if (array[mid]>target) { 
        return binarySearchRecursive(array, target, low, mid - 1); 
    } else { 
        return binarySearchRecursive(array, target, mid + 1, high); 
    } 
} 
  • 在递归实现中,每次递归调用都会缩小查找区间,直到找到目标元素或者确定目标元素不存在。递归实现的思路更加直观地体现了二分查找的分治思想,但由于递归调用会占用额外的栈空间,在数据量非常大时可能会导致栈溢出。

三、二分查找算法的复杂度分析

  1. 时间复杂度
    • 二分查找的时间复杂度是O(logn)O(logn)。假设数据集合的大小为nn,每次查找都会将查找区间缩小一半。可以将这个过程看作是一个等比数列,当n/2^k = 1n/2k=1(nn经过kk次缩小后变为1)时,kk的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了kk次区间缩小操作,时间复杂度就是O(k)O(k),这里k = log_2nk=log2​n。例如,当n = 2^{32}n=232(大约是42亿)时,如果我们在这么多数据中用二分查找一个数据,最多也只需要比较32次。引用自[1]“二分查找是一种非常高效的查找算法,其时间复杂度达到了惊人的O(logn)O(logn)。分析如下:。可以看出来,这是一个等比数列。其中n/2^k = 1n/2k=1时,kk的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了kk次区间缩小操作,时间复杂度就是O(k)O(k)。”
    • 这种对数时间复杂度是非常高效的,在大规模数据面前表现出色。甚至在某些情况下,比时间复杂度是常量级O(1)O(1)的算法还要高效。因为lognlogn是一个增长非常缓慢的函数,即便nn非常非常大,对应的lognlogn也很小。而且在使用大O标记法表示时间复杂度的时候,会省略掉常数、系数和低阶。对于常量级时间复杂度的算法来说,O(1)O(1)有可能表示一个非常大的常量值,比如O(1000)O(1000)、O(10000)O(10000)。
  2. 空间复杂度
    • 对于循环实现的二分查找,其空间复杂度是O(1)O(1),因为只需要使用几个额外的变量(如lowhighmid等)来记录查找区间和中间位置,这些变量所占用的空间不随数据规模nn的增长而增长。
    • 对于递归实现的二分查找,空间复杂度是O(logn)O(logn)。因为递归调用的最大深度是lognlogn(每次递归都会将查找区间缩小一半),每个递归调用都会占用一定的栈空间,所以总的空间复杂度是O(logn)O(logn)。

四、二分查找算法的变体

  1. 查找第一个等于目标值的元素
    • 在有序数组中可能存在多个等于目标值的元素,有时候我们需要找到第一个等于目标值的元素。以下是一种实现方式:
int findFirstEqual(std::vector<int>&vec, intvalue) { 
    intlow = 0, high = vec.size()  - 1; 
    int result = - 1; 
    while (low <= high) { 
        intmid = low+((high - low)/2); 
        if (vec[mid]==value) { 
            result = mid; 
            high = mid - 1; 
        } else if (vec[mid]>value) { 
            low = mid + 1; 
        } else { 
            high = mid - 1; 
        } 
    } 
    return result; 
} 
  • 在这个实现中,当找到一个等于目标值的元素时,我们不立即返回,而是继续在当前元素的左边查找,看是否还有等于目标值的元素,直到确定当前元素就是第一个等于目标值的元素。
  1. 查找最后一个等于目标值的元素
    • 类似地,要找到最后一个等于目标值的元素,可以使用以下实现方式:
int findLastEqual(std::vector<int>&vec, intvalue) { 
    intlow = 0, high = vec.size()  - 1; 
    int result = - 1; 
    while (low <= high) { 
        intmid = low+((high - low)/2); 
        if (vec[mid]==value) { 
            result = mid; 
            low = mid + 1; 
        } else if (vec[mid]>value) { 
            low = mid + 1; 
        } else { 
            high = mid - 1; 
        } 
    } 
    return result; 
} 
  • 这里当找到等于目标值的元素时,继续在当前元素的右边查找,确定是否还有等于目标值的元素,直到找到最后一个等于目标值的元素。
  1. 查找第一个大于目标值的元素
    • 实现如下:
int findFirstGreater(std::vector<int>&vec, intvalue) { 
    intlow = 0, high = vec.size()  - 1; 
    int result = - 1; 
    while (low <= high) { 
        intmid = low+((high - low)/2); 
        if (vec[mid]>value) { 
            result = mid; 
            high = mid - 1; 
        } else { 
            low = mid + 1; 
        } 
    } 
    return result; 
} 
  • 当找到一个大于目标值的元素时,记录下来并继续在左边查找是否还有更小的大于目标值的元素。
  1. 查找最后一个小于目标值的元素
    • 实现如下:
int findLastLess(std::vector<int>&vec, intvalue) { 
    intlow = 0, high = vec.size()  - 1; 
    int result = - 1; 
    while (low <= high) { 
        intmid = low+((high - low)/2); 
        if (vec[mid]<value) { 
            result = mid; 
            low = mid + 1; 
        } else { 
            high = mid - 1; 
        } 
    } 
    return result; 
} 
  • 当找到一个小于目标值的元素时,记录下来并继续在右边查找是否还有更大的小于目标值的元素。

五、二分查找与其他算法的比较

  1. 与线性查找的比较
    • 线性查找:线性查找是一种最基本的查找算法,它从数据集合的第一个元素开始,逐个比较元素与目标元素,直到找到目标元素或者遍历完整个数据集合。线性查找的时间复杂度是O(n)O(n),其中nn是数据集合的大小。例如,在一个未排序的数组中查找一个元素就只能使用线性查找。
    • 二分查找优势:与线性查找相比,二分查找的时间复杂度O(logn)O(logn)远远优于线性查找的O(n)O(n)。当数据量较大时,这种优势更加明显。例如,当n = 1000000n=1000000时,线性查找在最坏情况下需要比较1000000次,而二分查找最多只需要比较20次(log_21000000\approx20log2​1000000≈20)。然而,二分查找要求数据必须是有序的,而线性查找对数据的顺序没有要求。如果数据本身是无序的,并且不需要频繁查找,那么线性查找可能是一个更简单、更直接的选择。
  2. 与哈希表查找的比较
    • 哈希表查找:哈希表是一种根据关键码值(Key - value)而直接进行访问的数据结构。通过哈希函数将键映射到一个桶(bucket)中,理想情况下,哈希表查找的时间复杂度可以接近O(1)O(1)。例如,在一个存储用户信息的哈希表中,根据用户ID查找用户信息,只需要通过哈希函数计算出桶的位置,就可以直接获取到对应的信息。
    • 二分查找优势与劣势:二分查找的时间复杂度是O(logn)O(logn),虽然也是高效的,但相比哈希表查找的近似O(1)O(1)还是稍慢。然而,哈希表需要额外的空间来存储哈希函数、桶等信息,并且哈希函数的设计需要考虑避免哈希冲突等问题。而二分查找只需要在有序数组上进行操作,不需要额外的空间来存储复杂的结构。另外,二分查找适用于有序的静态数据,而哈希表更适合于动态数据的快速插入、删除和查找操作。

六、二分查找在实际中的应用

  1. 在数据库查询中的应用
    • 在数据库管理系统中,当对有序的索引列进行查询时,二分查找的思想常常被用到。例如,在一个按照用户年龄排序的用户表索引中查找特定年龄的用户,数据库可以利用二分查找快速定位到可能包含目标用户的索引块,然后在这个块内进一步查找具体的用户记录。这样可以大大提高查询的效率,减少磁盘I/O操作的次数。
  2. 在算法竞赛中的应用
    • 在算法竞赛中,二分查找及其变体经常被用来解决各种类型的问题。比如,在一些需要在给定区间内找到满足某种条件的最优解的问题中,可以将问题转化为二分查找的形式。例如,给定一个函数f(x)f(x),它在某个区间[a,b][a,b]上是单调递增或者单调递减的,要求找到使得f(x)=kf(x)=k的xx的值,就可以使用二分查找来解决。先确定一个初始的查找区间,然后根据函数值与目标值kk的比较结果不断缩小查找区间,直到找到满足条件的xx。
  3. 在计算机图形学中的应用
    • 在计算机图形学中,二分查找可以用于一些图形渲染和几何计算方面的优化。例如,在对一个复杂的三维模型进行光线追踪时,需要确定光线与模型表面的交点。如果对模型的表面三角形进行某种排序(比如按照距离光源的远近排序),就可以使用二分查找来快速定位可能与光线相交的三角形区域,从而减少不必要的计算,提高渲染的效率。

七、二分查找的局限性

  1. 数据必须有序
    • 二分查找的一个最大局限性就是要求数据必须是有序的。如果数据是无序的,就需要先对数据进行排序操作,而排序操作本身可能会消耗大量的时间和空间。例如,对于一个包含nn个元素的数组,如果使用快速排序算法进行排序,其平均时间复杂度是O(nlogn)O(nlogn),这在某些实时性要求较高的场景下可能是不可接受的。
  2. 不适合动态数据结构
    • 二分查找通常是在数组这种静态数据结构上进行操作的。对于动态数据结构,如链表,由于无法直接通过下标快速访问中间元素,二分查找就不适用了。在链表中查找一个元素,通常只能使用线性查找,从链表的头节点开始逐个节点进行查找。即使链表中的数据是有序的,也很难实现像在数组中那样高效的二分查找操作。
  3. 数据量较小时优势不明显
    • 当数据量较小时,二分查找的O(logn)O(logn)时间复杂度相对于线性查找的O(n)O(n)时间复杂度的优势并不十分明显。例如,当n = 10n=10时,线性查找最多需要比较10次,而二分查找最多需要比较log_210\approx3.32log2​10≈3.32,向上取整为4次。在这种情况下,由于二分查找的实现相对复杂一些,可能线性查找会是一个更简单、更直接的选择。

八、总结

  1. 重要性
    • 二分查找作为一种经典的查找算法,在计算机科学领域有着广泛的应用。它的高效性(O(logn)O(logn)的时间复杂度)使得它在处理大规模有序数据时能够快速定位目标元素。无论是在数据库查询、算法竞赛,还是在计算机图形学等领域,二分查找都发挥着重要的作用。
  2. 发展与改进方向
    • 随着计算机技术的不断发展,对于二分查找算法的研究也在不断深入。一方面,对于二分查找算法的变体的研究,如如何更高效地实现各种变体(查找第一个等于、最后一个等于、第一个大于、最后一个小于目标值的元素等),以满足不同的实际需求。另一方面,在面对新兴的数据类型和存储结构时,如何将二分查找的思想进行扩展和应用也是一个研究方向。例如,在分布式存储系统中,如何利用二分查找来提高数据查找的效率等。同时,如何更好地结合其他算法和数据结构,发挥二分查找的最大优势也是未来研究的一个方向。

九、感想

假如你真的听懂了,那么,就做做这些题吧

二分查找题目专栏-东方博宜OJ

拜拜┏(^0^)┛

标签:二分,--,元素,mid,high,探究,查找,low
From: https://blog.csdn.net/hjxxlsx/article/details/143645595

相关文章

  • B. Replacement (python解)-codeforces
    B.Replacement(python解)-codeforces原题链接:B.Replacement问题分析:我们有两个二进制字符串:s(长度为n)和r(长度为n-1)。根据游戏规则,我们需要在s上执行n-1次操作。在每次操作中,我们选择一个索引k,使得s[k]和s[k+1]不相同并将这两个字符替换为r[i](第i次操作中r的......
  • 【最新原创毕设】基于移动端的助农电商系统+08655(免费领源码)可做计算机毕业设计JAVA、
    基于移动端的助农电商系统的设计与实现摘要近年来,电子商务的快速发展引起了行业和学术界的高度关注。基于移动端的助农电商系统旨在为用户提供一个简单、高效、便捷的农产品购物体验,它不仅要求用户清晰地查看所需信息,而且还要求界面设计精美,使得功能与页面完美融合,从而提升......
  • (2024最新毕设合集)基于SpringBoot的梓锦社区疫苗接种服务系统+42529|可做计算机毕业设
    目 录摘要1绪论1.1选题背景与意义1.2开发现状1.3论文结构与章节安排2 梓锦社区疫苗接种服务系统系统分析2.1可行性分析2.1.1技术可行性分析2.1.2 经济可行性分析2.1.3法律可行性分析2.2系统功能分析2.2.1功能性分析2.2.2非功能性分析2.......
  • 封装红黑树实现mymap和myset--C++
    源码及框架分析SGI-STL30版本源代码,map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。map和set的实现结构框架核心部分截取出来如下://set#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_set.h>#include<st......
  • 【计算机毕业设计选题推荐】基于springboot湖北汽车工业科技学院校园二手商品交易系统
    ✍✍计算机编程指导师⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流!⚡⚡Java实战|SpringBoot/SSMPython实战项目|Django微信小程......
  • 【C++】验证STL容器线程不安全
    文章目录概要整体架构流程技术名词解释技术细节示例代码代码现象分析代码来验证一下vector的扩容解决方法小结概要在并发编程中,线程安全是确保多个线程在同时访问共享资源时,不会引起数据竞争或意外的行为。在C++中,std::vector通常并不是线程安全的,因此在多线程环境......
  • ReactPress技术揭秘
    ReactPressGithub项目地址:https://github.com/fecommunity/reactpress欢迎Star。一、引言ReactPress是一个基于React构建的开源发布平台,它不仅可以帮助用户在支持React和MySQL数据库的服务器上快速搭建自己的博客或网站,还能作为一个功能强大的内容管理系统(CMS)使用。本......
  • 【计算机毕设选题推荐】基于javaee的超市外卖系统的设计与实现 【附源码+部署+讲解】
    ✍✍计算机编程指导师⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流!⚡⚡Java实战|SpringBoot/SSMPython实战项目|Django微信小程......
  • 实验4
    Task1#include<stdio.h>#defineN4#defineM2voidtest1(){ intx[N]={1,9,8,4}; inti; //输出数组x所占用的字节 printf("sizeof(x)=%d\n",sizeof(x)); //输出每个元素占据的地址以及值 for(i=0;i<N;i++) printf("%p:%d\n",&x[i],x[i]); //输出数组x对应的值 pri......
  • 实验4
    #include<stdio.h>#defineN4#defineM2voidtest1(){intx[N]={1,9,8,4};inti;printf("sizeof(x)=%d\n",sizeof(x));for(i=0;i<N;++i)printf("%p:%d\n",&x[i],x[i]);prin......