一、二分查找算法的基本概念
- 定义与原理
- 二分查找,也被称为折半查找,是一种在有序数据集合中查找特定元素的高效算法。其原理基于分治思想,每次查找都将查找区间缩小一半。例如,在一个有序数组中查找一个特定的数字,我们先比较数组中间位置的元素与目标元素的大小。如果中间元素等于目标元素,那么查找成功;如果中间元素大于目标元素,那么目标元素必然在数组的前半部分,我们就将查找区间缩小到数组的前半部分,然后继续在这个新的区间内进行同样的操作;如果中间元素小于目标元素,那么目标元素就在数组的后半部分,我们就将查找区间缩小到后半部分再进行查找。这种不断缩小查找区间的方式使得查找速度非常快。引用自[1]“二分查找是一种非常简单易懂的快速查找算法,生活中到处可见。”
- 适用场景
- 二分查找适用于有序的数据结构,比如有序数组。当数据量较大时,它的优势更加明显。例如,在一个包含大量有序用户信息(按照用户ID或者注册时间等排序)的数据库中查找特定用户的信息,使用二分查找可以快速定位到目标用户。如果数据是无序的,那么首先需要对数据进行排序,然后才能使用二分查找。
二、二分查找算法的实现
- 循环实现方式
- 在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
,就可能会发生死循环”。
- 循环退出条件:循环退出条件是
- 递归实现方式
- 除了使用循环来实现二分查找,还可以用递归来实现。以下是一个递归实现二分查找的伪代码示例:
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);
}
}
- 在递归实现中,每次递归调用都会缩小查找区间,直到找到目标元素或者确定目标元素不存在。递归实现的思路更加直观地体现了二分查找的分治思想,但由于递归调用会占用额外的栈空间,在数据量非常大时可能会导致栈溢出。
三、二分查找算法的复杂度分析
- 时间复杂度
- 二分查找的时间复杂度是O(logn)O(logn)。假设数据集合的大小为nn,每次查找都会将查找区间缩小一半。可以将这个过程看作是一个等比数列,当n/2^k = 1n/2k=1(nn经过kk次缩小后变为1)时,kk的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了kk次区间缩小操作,时间复杂度就是O(k)O(k),这里k = log_2nk=log2n。例如,当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)。
- 空间复杂度
- 对于循环实现的二分查找,其空间复杂度是O(1)O(1),因为只需要使用几个额外的变量(如
low
、high
、mid
等)来记录查找区间和中间位置,这些变量所占用的空间不随数据规模nn的增长而增长。 - 对于递归实现的二分查找,空间复杂度是O(logn)O(logn)。因为递归调用的最大深度是lognlogn(每次递归都会将查找区间缩小一半),每个递归调用都会占用一定的栈空间,所以总的空间复杂度是O(logn)O(logn)。
- 对于循环实现的二分查找,其空间复杂度是O(1)O(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;
}
- 在这个实现中,当找到一个等于目标值的元素时,我们不立即返回,而是继续在当前元素的左边查找,看是否还有等于目标值的元素,直到确定当前元素就是第一个等于目标值的元素。
- 查找最后一个等于目标值的元素
- 类似地,要找到最后一个等于目标值的元素,可以使用以下实现方式:
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;
}
- 这里当找到等于目标值的元素时,继续在当前元素的右边查找,确定是否还有等于目标值的元素,直到找到最后一个等于目标值的元素。
- 查找第一个大于目标值的元素
- 实现如下:
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;
}
- 当找到一个大于目标值的元素时,记录下来并继续在左边查找是否还有更小的大于目标值的元素。
- 查找最后一个小于目标值的元素
- 实现如下:
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;
}
- 当找到一个小于目标值的元素时,记录下来并继续在右边查找是否还有更大的小于目标值的元素。
五、二分查找与其他算法的比较
- 与线性查找的比较
- 线性查找:线性查找是一种最基本的查找算法,它从数据集合的第一个元素开始,逐个比较元素与目标元素,直到找到目标元素或者遍历完整个数据集合。线性查找的时间复杂度是O(n)O(n),其中nn是数据集合的大小。例如,在一个未排序的数组中查找一个元素就只能使用线性查找。
- 二分查找优势:与线性查找相比,二分查找的时间复杂度O(logn)O(logn)远远优于线性查找的O(n)O(n)。当数据量较大时,这种优势更加明显。例如,当n = 1000000n=1000000时,线性查找在最坏情况下需要比较1000000次,而二分查找最多只需要比较20次(log_21000000\approx20log21000000≈20)。然而,二分查找要求数据必须是有序的,而线性查找对数据的顺序没有要求。如果数据本身是无序的,并且不需要频繁查找,那么线性查找可能是一个更简单、更直接的选择。
- 与哈希表查找的比较
- 哈希表查找:哈希表是一种根据关键码值(Key - value)而直接进行访问的数据结构。通过哈希函数将键映射到一个桶(bucket)中,理想情况下,哈希表查找的时间复杂度可以接近O(1)O(1)。例如,在一个存储用户信息的哈希表中,根据用户ID查找用户信息,只需要通过哈希函数计算出桶的位置,就可以直接获取到对应的信息。
- 二分查找优势与劣势:二分查找的时间复杂度是O(logn)O(logn),虽然也是高效的,但相比哈希表查找的近似O(1)O(1)还是稍慢。然而,哈希表需要额外的空间来存储哈希函数、桶等信息,并且哈希函数的设计需要考虑避免哈希冲突等问题。而二分查找只需要在有序数组上进行操作,不需要额外的空间来存储复杂的结构。另外,二分查找适用于有序的静态数据,而哈希表更适合于动态数据的快速插入、删除和查找操作。
六、二分查找在实际中的应用
- 在数据库查询中的应用
- 在数据库管理系统中,当对有序的索引列进行查询时,二分查找的思想常常被用到。例如,在一个按照用户年龄排序的用户表索引中查找特定年龄的用户,数据库可以利用二分查找快速定位到可能包含目标用户的索引块,然后在这个块内进一步查找具体的用户记录。这样可以大大提高查询的效率,减少磁盘I/O操作的次数。
- 在算法竞赛中的应用
- 在算法竞赛中,二分查找及其变体经常被用来解决各种类型的问题。比如,在一些需要在给定区间内找到满足某种条件的最优解的问题中,可以将问题转化为二分查找的形式。例如,给定一个函数f(x)f(x),它在某个区间[a,b][a,b]上是单调递增或者单调递减的,要求找到使得f(x)=kf(x)=k的xx的值,就可以使用二分查找来解决。先确定一个初始的查找区间,然后根据函数值与目标值kk的比较结果不断缩小查找区间,直到找到满足条件的xx。
- 在计算机图形学中的应用
- 在计算机图形学中,二分查找可以用于一些图形渲染和几何计算方面的优化。例如,在对一个复杂的三维模型进行光线追踪时,需要确定光线与模型表面的交点。如果对模型的表面三角形进行某种排序(比如按照距离光源的远近排序),就可以使用二分查找来快速定位可能与光线相交的三角形区域,从而减少不必要的计算,提高渲染的效率。
七、二分查找的局限性
- 数据必须有序
- 二分查找的一个最大局限性就是要求数据必须是有序的。如果数据是无序的,就需要先对数据进行排序操作,而排序操作本身可能会消耗大量的时间和空间。例如,对于一个包含nn个元素的数组,如果使用快速排序算法进行排序,其平均时间复杂度是O(nlogn)O(nlogn),这在某些实时性要求较高的场景下可能是不可接受的。
- 不适合动态数据结构
- 二分查找通常是在数组这种静态数据结构上进行操作的。对于动态数据结构,如链表,由于无法直接通过下标快速访问中间元素,二分查找就不适用了。在链表中查找一个元素,通常只能使用线性查找,从链表的头节点开始逐个节点进行查找。即使链表中的数据是有序的,也很难实现像在数组中那样高效的二分查找操作。
- 数据量较小时优势不明显
- 当数据量较小时,二分查找的O(logn)O(logn)时间复杂度相对于线性查找的O(n)O(n)时间复杂度的优势并不十分明显。例如,当n = 10n=10时,线性查找最多需要比较10次,而二分查找最多需要比较log_210\approx3.32log210≈3.32,向上取整为4次。在这种情况下,由于二分查找的实现相对复杂一些,可能线性查找会是一个更简单、更直接的选择。
八、总结
- 重要性
- 二分查找作为一种经典的查找算法,在计算机科学领域有着广泛的应用。它的高效性(O(logn)O(logn)的时间复杂度)使得它在处理大规模有序数据时能够快速定位目标元素。无论是在数据库查询、算法竞赛,还是在计算机图形学等领域,二分查找都发挥着重要的作用。
- 发展与改进方向
- 随着计算机技术的不断发展,对于二分查找算法的研究也在不断深入。一方面,对于二分查找算法的变体的研究,如如何更高效地实现各种变体(查找第一个等于、最后一个等于、第一个大于、最后一个小于目标值的元素等),以满足不同的实际需求。另一方面,在面对新兴的数据类型和存储结构时,如何将二分查找的思想进行扩展和应用也是一个研究方向。例如,在分布式存储系统中,如何利用二分查找来提高数据查找的效率等。同时,如何更好地结合其他算法和数据结构,发挥二分查找的最大优势也是未来研究的一个方向。
九、感想
假如你真的听懂了,那么,就做做这些题吧