算法 - 二进制搜索
最编程
2024-07-07 10:20:05
...
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下:
(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。
(2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。
(3)如果某一步数组为空,则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
非递归算法:
function binarySearch(arr,key){
var low=0; //数组最小索引值
var high=arr.length-1; //数组最大索引值
while(low<=high){
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key>arr[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return -1; //low>high的情况,这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}
结果测试:
递归算法:
function binarySearch(arr,low,high,key){
if(low>high){return -1;}
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key<arr[mid]){
high=mid-1;
return binarySearch(arr,low,high,key);
}else{
low=mid+1;
return binarySearch(arr,low,high,key);
}
}
结果测试:
上一篇: 折半查找法(二分法)的 C 语言实现
下一篇: C 语言详细解释了二进制搜索的用法
推荐阅读
-
专题十二_洪水灌溉算法_算法专题详细摘要-7.壁橱组织(中型)
-
平衡二叉树(AVL 树)的二叉树算法详解
-
聚类分析 | IPOA 优化 FCM 模糊 C 均值聚类优化算法 - 基本介绍
-
排序算法(2)
-
LeetCode] 动态编程 - 95.动态编程 - 95.不同的二叉搜索树 II(附完整 Python/C++ 代码) - 基本思想
-
数据结构 图的邻接表表示法 有向 + 无向图的深度优先搜索遍历(C 代码 + 终端输入内容)
-
卡丹算法
-
随机森林算法 + SHAP 值(随机森林)
-
代码随机化算法训练营第 15 天|第 15 天 二叉树
-
[算法] 动态程序设计类 (2) - 01 背包 + 完整背包(注释)