算法学习:二分查找

简介: 算法学习:二分查找

🔥 引言

在现代计算机科学与软件工程的实践中,高效数据检索是众多应用程序的核心需求之一。二分查找算法,作为解决有序序列查询问题的高效策略,凭借其对数时间复杂度的优越性能,占据着算法领域里举足轻重的地位。本篇内容旨在全面剖析二分查找算法的内在机制、实施步骤、性能特点及其在实际应用中的考量,为深入理解和有效应用此算法提供坚实的基础。📚


🌐 基础概念入门

什么是二分查找❓

想象一下,你站在一列整齐排列的书架前,想要找到某本书。

传统的做法是从头开始一本本地找,但如果你知道书架上的书是按字母顺序排列的,聪明的做法是直接走到中间,如果目标书在中间就找到了,不在的话根据书名比较判断是在左边还是右边的书架继续寻找。这就是二分查找的基本思想。🔍

如何工作❓

  • 有序数组:二分查找的前提是数组必须是有序的,无论是升序还是降序。
  • 分而治之:算法每次都将搜索区间缩小一半,通过比较中间元素来决定是在左半部分还是右半部分继续查找。
  • 递归或迭代:二分查找可以递归或迭代实现,选择哪种方式取决于个人偏好和具体应用场景。

工作示例

下面的示例说明了二分查找的工作原理。我随便想一个 1~100 的数字。你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。假设你从 1 开始依次往上猜,猜测过程会是这样。

这是 简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字,在最糟糕的情况下需要100次才能够找到这个数字。

而二分查找直接从有序列表的中间开始,一次就将排除一半的数字:

随后再从剩下的数字(50-100)的中间数(75)进行判断,又将排除掉一半的数字:

随后再从数字(50-75)的中间数进行判断,以此类推:找到最后的数:

也就是说,100个元素的情况,使用二分查找最糟糕的情况也只需要7步就可以查找到相应的数字,比简单查找要少多了!

上述示例来自 力扣——算法图解

🔍 算法步骤详述

  1. 初始化指针:设置两个指针,left初始为0,表示数组起始位置;right初始为数组最后一个元素的索引。
  2. 计算中间索引:为了避免整数溢出,通常采用mid = left + (right - left) / 2
  3. 比较并调整区间
  • array[mid] == target,直接返回mid
  • array[mid] < target,说明目标在右半部分,更新left = mid + 1
  • array[mid] > target,则目标在左半部分,更新right = mid - 1
  1. 重复步骤2和3,直到left > right,此时说明数组中不存在目标值,返回-1或其他表示未找到的值。

🧩 进阶理解

📌 大O表示法与时间复杂度分析

在深入探讨二分查找之前,了解大O表示法这一衡量算法效率的重要工具是不可或缺的。大O表示法用于描述算法在最坏情况下的时间复杂度,即随着输入数据量增长,算法执行时间增长的速度。它关注的是上界分析,帮助我们理解算法在大规模数据处理时的性能表现。

🍭 大O表示法简介
  • 符号意义:“O”表示“Order of”,用来描述算法运行时间的增长率
  • 重点在于增速:它并不精确测量算法执行的确切时间,而是关注于当输入大小(通常用n表示)增加时,算法执行时间增长的速率。
  • 简化原则:忽略常数因子和低阶项,专注于最高阶项,因为当n足够大时,这些因素对整体趋势影响不大。

大 O 表示法指出了算法有多快。例如,假设列表包含n个元素。简单查找需要检查每个元素,因此需要执行n次操作。使用大 O 表示法,这个运行时间为 𝑂(𝑛)。单位秒呢?没有——大 O 表示法指的并非以秒为单位的速度。大 O 表示法让你能够比较操作数,它指出了算法运行时间的增速

🍭 二分查找的时间复杂度

对于二分查找算法,每次迭代都将搜索区间减半,这意味着查找次数与输入数据的对数成正比。因此,二分查找的时间复杂度为O(log n)

🍭 与简单查找对比

为了更好地理解二分查找的效率,我们可以将其与简单(顺序/线性)查找进行对比:

  • 简单查找(也称顺序/线性查找):在无序或有序列表中从头到尾遍历,直到找到目标值或遍历完整个列表。其时间复杂度为𝑂(𝑛),意味着随着数据量的增加,查找时间线性增长。
  • 二分查找在有序列表中通过不断缩小搜索范围来查找目标值。时间复杂度为𝑂(log 𝑛),表明当数据量翻倍时,所需查找步骤仅增加log(𝑛)次,这是一种远低于线性增长的速度。
🍭 时间增速对比
  • 简单查找的时间增速与数据量成正比,直观理解就是数据每增加一倍,查找时间大致也增加一倍。在大数据集上,这种增长速度很快变得不可承受。
  • 二分查找的时间增速则要慢得多,因为它基于对数函数。例如,即使数据量从1000增加到100万,二分查找所需的步骤只增加大约从10增加到20(基于2为底的对数),这种增长速率在处理大量数据时显得极为高效。

如图所示:假如查找100个元素使用简单查找需要100毫秒,使用二分查找需要7毫秒,可能这个差距可以让人接受。当数据增多时,查找1000000000个元素需要11天才可以查找完毕,而使用二分查找仅仅只需要30毫秒,比使用简单查找查询100个元素还要快的多!

简单查找(也称为顺序查找)的时间复杂度为𝑂(𝑛),这意味着如果数据量增加,查找所需的时间也会直接线性地增加:

二分查找的时间复杂度为𝑂(log 𝑛),这意味着随着数据量n的增大,二分查找所需时间的增速远低于线性查找,它与数据量的对数成正比,而非与数据量本身成正比:

综上所述,二分查找由于其对数级的时间复杂度,在处理大规模有序数据集时,相比线性查找有着显著的性能优势,特别是在数据规模庞大的情况下,这种优势体现得更为明显。


📈 实践案例:JavaScript代码示例

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

/**
 * @param {number[]} nums  // 传入一个有序的整型数组nums
 * @param {number} target  // 需要查找的目标值target
 * @return {number}         // 返回目标值在数组中的索引,如果未找到则返回-1
 */
const search = function (nums, target) {
  let left = 0, right = nums.length - 1;  // 初始化左右边界,left为数组起始索引,right为数组结束索引
  let result = -1;  // 初始化结果变量result为-1,表示目标值未找到
  // 当左边界小于等于右边界时,继续循环
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2);  // 计算中间索引mid,使用Math.floor向下取整保证mid为整数
    // 如果中间元素等于目标值
    if (nums[mid] === target) {
      result = mid;  // 更新result为找到的目标值索引
      right = mid - 1;  // 调整右边界继续在左半部分查找(若需查找重复值应调整此处逻辑)
    }
    // 如果中间元素小于目标值
    else if (nums[mid] < target) {
      left = mid + 1;  // 缩小查找范围至右半部分,更新左边界
    }
    // 如果中间元素大于目标值
    else {
      right = mid - 1;  // 缩小查找范围至左半部分,更新右边界
    }
  }
  return result;  // 循环结束,返回最终查找结果
};
// 示例使用
const sortedArray = [-1,0,3,5,9,12];  // 定义一个已排序的数组
console.log(search(sortedArray, 9));  // 在数组中查找数字9,并打印查找结果为 4

📌 总结

二分查找算法是针对有序数组高效查找特定元素的方法。其核心机制在于每次比较数组中间元素,根据比较结果将查找范围减半,直至找到目标或确定目标不存在。这一过程展现了𝑂(log 𝑛)的时间复杂度,意味着数据量每翻一倍,查找操作的次数只需增加一个固定比例(基于对数增长),而非线性增长。相比之下,线性查找的时间复杂度为𝑂(𝑛),数据量增长时效率下降明显。

大O表示法作为衡量算法效率的标准,帮助我们抽象理解算法随输入规模变化的性能表现,关注上界分析,忽略了常数项和低阶项,专注于影响最大的部分。在算法设计与分析中,它是评估和比较不同方案效率的有力工具。

总之,二分查找凭借其对数时间复杂度,在处理大规模有序数据时表现出色,是算法工具箱中不可或缺的高效利器。而对于任何算法的学习,理解大O表示法都是基础且关键的一步,它让我们能够科学地预测和优化程序的执行效率。

目录
相关文章
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
13天前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!