文章编号：18824 / 分类：互联网资讯 / 更新时间：2024-07-23 17:29:41 / 浏览：次

二分查找 (也称为折半查找) 是一种高效的查找算法，用于在有序数组或列表中找到特定元素。该算法通过将搜索空间不断对半分，从而快速找到目标元素。

算法步骤

1. 确定数组的中间元素 m 。
2. 将目标元素与 m 比较：
若目标元素等于 m ，则算法结束，找到了目标元素。若目标元素小于 m ，则算法在数组的左半部分继续查找（即 [0, m-1] ）。若目标元素大于 m ，则算法在数组的右半部分继续查找（即 [m+1, n-1] ，其中 n 是数组的长度）。
3. 重复步骤 1 和 2，直到找到目标元素或搜索空间为空。

时间复杂度

二分查找的时间复杂度为 O(log n) ，其中 n 是数组的长度。这是因为算法每次将搜索空间对半分，从而将搜索时间减少一半。

示例

考虑以下有序数组：```arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]```若要查找元素 7 ，算法将执行以下步骤：

1. 中间元素为 m = 5。
2. 7 < 5，因此算法在左半部分继续查找（即 [0,4] ）。
3. 中间元素为 m = 2。
4. 7 > 2，因此算法在右半部分继续查找（即 [3, 4] ）。
5. 中间元素为 m = 3。
6. 7 = 3，算法找到目标元素并结束。

代码实现

以下是用 Python 实现的二分查找算法：```pythondef binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1 目标元素不在数组中```

优点

时间复杂度为 O(log n) ，非常高效。适用于有序数组或列表。易于实现和理解。

缺点

要求数组有序。如果数组非常大，则递归深度可能会成为问题。

应用

二分查找广泛应用于各种计算机科学领域，包括：在数据库中搜索记录在文件系统中查找文件在内存中查找特定值

结论

二分查找是一种高效且易于实现的算法，用于在有序数组或列表中快速找到特定元素。其 O(log n) 的时间复杂度使其适用于需要快速查找的大型数据集。

---

二分查找法

二分查找法的解释如下：

二分查找法也称折半查找法，是一种在有序数组中查找某一特定元素的搜索算法。 我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。

如果想要在数组中查找一个数，最基本的方法就是暴力解法：一次遍历，这时候时间复杂度是O（N），二分查找就是其中的一种优化，时间复杂度是O（logN）；具体做法是一步一步逼近直到找到。 前提是数组需要是一个排序数组。

查找过程：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。

否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

算法要求：

1、必须采用顺序存储结构。

2、必须按关键字大小有序排列。

比较次数

计算公式：

当顺序表有n个关键字时：

查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

注意：a，b，n均为正整数。

按二分查找法进行查找，查找长度为4的元素的下标是多少？

在有序表a［1…20］中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是10，5，3，4。

二分查找是将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 因此为（1＋20）／2取10，大于4，查1到10；（1＋10）／2取5，大于4，查1到5；（1＋5）／2取，取3，小于4，查3到5；（3＋5）／2取4，找到4。

扩展资料：

二分查找法的基本思想是将n个元素分成大致相等的两部分，取a［n／2］与x做比较，如果x＝a［n／2］，则找到x，算法中止；如果x

二分查找法充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O（log n）完成搜索任务。

什么叫Java中的二分查找法

算法概念，二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法，这种算法是建立在有序数组基础上的；算法思想，搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束，如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都使搜索范围缩小一半。 实现思路，找出位于数组中间的值，并存放在一个变量中，变量暂时命名为temp，需要找到的key和temp进行比较，如果key值大于temp，则把数组中间位置作为下一次计算的起点，重复前面两步，如果key值小于temp，则把数组中间位置作为下一次计算的终点，重复前面三步，如果key值等于temp，则返回数组下标，完成查找。

相关标签： 二分查找法、 二分查找、

本文地址：https://www.badfl.com/article/9e6b469a3f7a418daa06.html

上一篇：web开发网web开发网页上有错误...
下一篇：vectorc用法vector机器人...