1、介绍

二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤：
（1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
（3）如果某一步数组为空，则表示找不到目标元素。

2、非递归算法

  1. function binary_search(arr, key) {
  2.   var low = 0,
  3.   high = arr.length - 1;
  4.   while(low <= high){
  5.     var mid = parseInt((high + low) / 2);
  6.     if(key == arr[mid]){
  7.         return  mid;
  8.     }else if(key > arr[mid]){
  9.         low = mid + 1;
  10.     }else if(key < arr[mid]){
  11.         high = mid -1;
  12.     }else{
  13.       return -1;
  14.     }
  15.   }
  16. };
  17. var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
  18. var result = binary_search(arr,10);
  19. console.log(result); // 9 返回目标元素的索引值

3、递归算法

  1. function binary_search(arr,low, high, key) {
  2.   if (low > high){
  3.     return -1;
  4.   }
  5.   var mid = parseInt((high + low) / 2);
  6.   if(arr[mid] == key){
  7.     return mid;
  8.   }else if (arr[mid] > key){
  9.     high = mid - 1;
  10.     return binary_search(arr, low, high, key);
  11.   }else if (arr[mid] < key){
  12.     low = mid + 1;
  13.     return binary_search(arr, low, high, key);
  14.   }
  15. };
  16. var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
  17. var result = binary_search(arr, 0, 13, 10);
  18. alert(result); // 9 返回目标元素的索引值