JavaScript二分查找算法原理与代码实现详解

二分查找算法概述

本文通过具体实例解析JavaScript中折半查找（即二分查找）算法的核心原理与代码实现方式，供读者参考学习。

问题描述与注意事项

一、问题描述：

目标是在一个已排序（升序）的数组中，利用折半查找算法确定指定数值所在的索引位置。例如：

var a=[1,2,3,4,5,6,7,8,9];
search(a,3);//返回2
search(a,1);//左边界，返回0
search(a,9);//右边界，返回8
search(a,0);//比最小的值还小，返回"您查找的数值不存在"
search(a,10);//比最大的值还大，返回"您查找的数值不存在"

注意：折半查找算法仅适用于有序数组，无序数组无法使用该方式进行搜索。例如在[10,5,6,7,8,9,20]中查找数值10，若中间索引对应的值为7，因7小于10，算法会转向右侧子数组继续查找，但实际在该范围内并不存在10。

代码实现与逻辑解析

二、我的实现

function search(arr,num) {
  var l=arr.length;
  var left=0;
  var right=l-1;
  var center=Math.floor((left+right)/2);
  while(left<=l-1&&right>=0){
    if (arr[center]==num) return center;
    if (left==right) return "您查找的数不存在";
    if (arr[center]>num) {
      right=center-1;
      center=Math.floor((left+right)/2);
    }else if (arr[center]<num) {
      left=center+1;
      center=Math.floor((left+right)/2);
    }
  }
}
var a=[1,2,3,4,5,6,7,8,9];
console.log(search(a,-2));

实现说明：

1、基本思路：

每次迭代比较数组中间索引处的值与目标值：若中间值大于目标值，则在中间位置左侧的子数组中继续查找；若中间值小于目标值，则在右侧子数组中查找；若两者相等，则直接返回当前中间索引。

2、变量定义：left表示查找范围的起始索引，right表示结束索引，center表示当前查找范围的中间索引。

3、while循环内的逻辑说明：

（1）由于查找次数不确定，使用while循环更为合适；

（2）循环终止条件包括：

a、当right小于0时，停止查找，因为此时已无有效范围。例如在a=[1,2,3,4,5,6,7,8,9]中查找0，当查找范围缩小至left=0、right=0、center=0时，进入while循环判断，由于arr[center]>0成立，故执行

right=center-1;
center=Math.floor((left+right)/2);

得到right=-1，此时应退出循环；

b、当left>l-1成立时，同样停止查找。例如在a=[1,2,3,4,5,6,7,8,9]中查找10，当范围变为left=8、right=8、center=8时，进入while循环，由于arr[center]<10成立，故执行

left=center;
center=Math.floor((left+right)/2);

得到left=9，此时应退出循环；

4、始终通过center索引处的值与目标值进行匹配；

5、Math.floor函数处理了查找范围长度为偶数时的取整问题；

6、当left==right成立，但arr[center]==num未执行时，可判定目标值不存在；

7、当arr[center]==num成立时，函数直接返回结果，后续代码不再执行。

上述代码已通过在线HTML/CSS/JavaScript代码运行工具http://tools.jb51.net/code/HtmlJsRun测试，运行结果如下：

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述的实现方法对JavaScript程序设计有所帮助。