Home  >  Article  >  Web Front-end  >  Sharing about JS binary search algorithm and code

Sharing about JS binary search algorithm and code

零到壹度
零到壹度Original
2018-03-20 11:20:521531browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn