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

 

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

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。因为如果low和high比较大的话，两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high - low)/2。因为相比除法运算来说，计算机处理位运算要快得多。引用自[1]“不能写成，mid=(low + high)/2。因为如果low和high比较大的话，两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high - low)/2”。
  • low和high的更新：low = mid+1，high = 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)，因为只需要使用几个额外的变量（如low、high、mid等）来记录查找区间和中间位置，这些变量所占用的空间不随数据规模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＾)┛