js二分查找算法介绍和代码分享
程序员文章站
2022-03-14 23:17:22
...
js二分查找算法介绍和代码分享
4.1 二分查找
算法介绍
二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤:
(1)首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
(2)如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。
(3)如果某一步数组为空,则表示找不到目标元素。
参考代码:
非递归算法
function binary_search(arr,key){
var low=0,
high=arr.length-1;
while(low<=high){
var mid=parseInt((high+low)/2);
if(key==arr[mid]){
return mid;
}else if(key>arr[mid]){
low=mid+1;
}else if(key<arr[mid]){
high=mid-1;
}else{
return -1;
}
}
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,10);
alert(result); // 9 返回目标元素的索引值
递归算法
function binary_search(arr,low,high,key){
if(low>high){
return -1;
}
var mid=parseInt((high+low)/2);
if(arr[mid]==key){
return mid;
}else if(arr[mid]>key){
high=mid-1;
return binary_search(arr,low,high,key);
}else if(arr[mid]<key){
low=mid+1;
return binary_search(arr,low,high,key);
}
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,0,13,10);
alert(result); // 9 返回目标元素的索引值
作者:极客教程
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇: 师兄帮帮忙 UVa 12412
下一篇: MD5 . SHA1 加密