Home > Article > Web Front-end > Sharing about JS binary search algorithm and code
This article mainly shares with you the JS binary search algorithm and code. Friends who need it can refer to it. I hope it can help everyone.
4.1 Binary search
Algorithm introduction
Binary search, also known as half search, is a search algorithm for finding specific elements in an ordered array. The search process can be divided into the following steps:
(1) First, start searching from the middle element of the ordered array. If the element happens to be the target element (that is, the element to be found), the search process ends, otherwise proceed to the next step. step.
(2) If the target element is greater than or less than the middle element, search in the half of the array that is greater than or less than the middle element, and then repeat the first step.
(3) If the array at a certain step is empty, it means that the target element cannot be found.
Reference code:
Non-recursive algorithm
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 返回目标元素的索引值
Recursive algorithm
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 返回目标元素的索引值
The above is the detailed content of Sharing about JS binary search algorithm and code. For more information, please follow other related articles on the PHP Chinese website!