二分查找法 (二分查找法是什么意思)

文章编号：18817 / 分类：技术教程 / 更新时间：2024-07-23 17:10:55 / 浏览：次

定义

二分查找法，又称折半查找法，是一种高效的查找算法。它适用于已经有序的数组或序列中查找元素。

原理

二分查找法的原理是：首先将目标数组或序列的中间元素作为比较元素。若目标元素等于比较元素，则查找成功。若目标元素小于比较元素，则说明目标元素一定在前半部分；若目标元素大于比较元素，则说明目标元素一定在后半部分。这样，就可以将目标元素的查找范围缩小到目标数组或序列的一半。

算法步骤

令数组或序列的左右边界为 low 和 high，初始值为 low = 0，high = 长度 - 1。
计算数组或序列的中间元素 mid = (low + high) / 2。
比较目标元素与中间元素：
- 若相等，则查找成功，返回 mid。
- 若小于，则目标元素一定在前半部分，设置 high = mid - 1。
- 若大于，则目标元素一定在后半部分，设置 low = mid + 1。
重复步骤 2-3，直到 low 大于 high。
若 low 大于 high，则查找失败，返回 -1。

代码实现

def 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)，其中 n 是数组或序列的长度。

应用场景

二分查找法广泛应用于各种场景，例如：

有序数组中查找元素
有序列表中查找值
查找有序数据结构（如二叉搜索树）中的元素
数据库中的快速查找

优缺点

优点：

时间复杂度低
适用于已经有序的数组或序列
代码实现简单

缺点：

要求数组或序列必须有序
对于无序数据，需要先进行排序操作

变种

插值查找法：通过线性插值的方式估计中间元素的位置，进一步提高查找效率。
斐波那契查找法：利用斐波那契数列来确定中间元素的位置，适用于查找范围未知或较大的情况。

总结

二分查找法是一种高效的查找算法，适用于已经有序的数组或序列中查找元素。它具有时间复杂度低、代码实现简单的优点，广泛应用于各种场景。

什么叫java中的二分查找法

1、算法概念。

二分查找算法也称为折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。

2、算法思想。

①搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

②如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

③如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

3、实现思路。

①找出位于数组中间的值，并存放在一个变量中（为了下面的说明，变量暂时命名为temp）；

②需要找到的key和temp进行比较；

③如果key值大于temp，则把数组中间位置作为下一次计算的起点；重复① ②。

④如果key值小于temp，则把数组中间位置作为下一次计算的终点；重复① ② ③。

⑤如果key值等于temp，则返回数组下标，完成查找。

4、实现代码。

/***description:二分查找。*@paramarray需要查找的有序数组*@paramfrom起始下标*@paramto终止下标*@paramkey需要查找的关键字*@return*/publicstatic>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{if(from<0||to<0){thrownewIllegalArgumentException(paramsfrom&lengthmustlargerthan0.);}if(from<=to){intmiddle=(from>>>1)+(to>>>1);//右移即除2Etemp=array[middle];if((key)>0){to=middle-1;}elseif((key)<0){from=middle+1;}else{returnmiddle;}}returnbinarySearch(array,from,to,key);}

什么是二分查找〉

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。使用条件：查找序列是顺序结构，有序。

过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

利用循环的方式实现二分法查找

public class BinarySearch {public static void main(String[] args) {// 生成一个随机数组int[] array = suiji();// 对随机数组排序(array);(产生的随机数组为： + (array));(要进行查找的值： );Scanner input = new Scanner();// 进行查找的目标值int aim = ();// 使用二分法查找int index = binarySearch(array, aim);(查找的值的索引位置： + index);}/** * 生成一个随机数组 ** @return 返回值，返回一个随机数组 */private static int[] suiji() {// (n)+m 返回m到m+n-1之间的随机数int n = new RanDOM()(6) + 5;int[] array = new int[n];// 循环遍历为数组赋值for (int i = 0; i < ; i++) {array[i] = new Random()(100);}return array;}/** * 二分法查找 ---循环的方式实现 ** @param array 要查找的数组 * @param aim 要查找的值 * @return 返回值，成功返回索引，失败返回-1 */private static int binarySearch(int[] array, int aim) {// 数组最小索引值int left = 0;// 数组最大索引值int right = - 1;int mid;while (left <= right) {mid = (left + right) / 2;// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围if (aim < array[mid]) {right = mid - 1;// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围} else if (aim > array[mid]) {left = mid + 1;// 若查找数据与中间元素值正好相等，则放回中间元素值的索引 } else {return mid;}}return -1;}}运行结果展示：

由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。

四、利用递归的方式实现二分法查找

public class BinarySearch2 {public static void main(String[] args) {// 生成一个随机数组int[] array = suiji();// 对随机数组排序(array);(产生的随机数组为： + (array));(要进行查找的值： );Scanner input = new Scanner();// 进行查找的目标值int aim = ();// 使用二分法查找int index = binarySearch(array, aim, 0, - 1);(查找的值的索引位置： + index);}/** * 生成一个随机数组 * * @return 返回值，返回一个随机数组 */private static int[] suiji() {// (n)+m 返回m到m+n-1之间的随机数int n = new Random()(6) + 5;int[] array = new int[n];// 循环遍历为数组赋值for (int i = 0; i < ; i++) {array[i] = new Random()(100);}return array;}/** * 二分法查找 ---递归的方式 * * @param array 要查找的数组 * @param aim要查找的值 * @param left 左边最小值 * @param right 右边最大值 * @return 返回值，成功返回索引，失败返回-1 */private static int binarySearch(int[] array, int aim, int left, int right) {if (aim < array[left] || aim > array[right]) {return -1;}// 找中间值int mid = (left + right) / 2;if (array[mid] == aim) {return mid;} else if (array[mid] > aim) {//如果中间值大于要找的值则从左边一半继续递归return binarySearch(array, aim, left, mid - 1);} else {//如果中间值小于要找的值则从右边一半继续递归return binarySearch(array, aim, mid + 1, -1);}}}运行结果展示：

总结：

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~