JavaScript实现二分查找法

2018-01-23

JavaScript实现二分查找法

二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法

使用递归的方法

弊端:当递归次数非常大的时候，浏览器会报堆栈溢出的错 什么是堆栈溢出？怎么处理堆栈溢出

/**
 * 从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束。否则进行下一步; 
 * 如果指定要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作
 * 重复以上过程，直到找到目标元素的索引，查找成功;或者直到子数组为空，查找失败
 * @param {any} data --要查找的有序数组 
 * @param {any} key --查找的的目标值
 * @param {any} start --开始查找的数组下标
 * @param {any} end --结束查找的数组下标
 */
function binarySearch(data, key, start, end) {
    start = start || 0;
    end = end || data.length - 1;
    var _binaryIndex = Math.floor((start + end) / 2);
    // 递归出口条件
    if (start > end) {
        // 如果该数组没有找到该key,则返回距离其最近的上一个值的索引号
        return end;
        // // 如果该数组没有找到该key,则返回距离其最近的下一个值的索引号
        // return start;
        // // 如果该数组没有找到该key,则返回-1
        // return -1;
    }
    if (key == data[_binaryIndex]) {
        return _binaryIndex;
    } else {
        if (key < data[_binaryIndex]) {
            return binarySearch(data, key, start, _binaryIndex - 1);
        }
        else {
            return binarySearch(data, key, _binaryIndex + 1, end);
        }
    }
}
var arr = [-34, 1, 3, 4, 5, 8, 34, 45, 65, 87];        
console.log("索引是:"+binarySearch(arr,7));

使用非递归的方法

/**
 * [binarySearch description]
 * @Author   lupinggan
 * @DateTime 2018-01-22T23:06:22+0800
 * @param    {[type]}                 data [description]
 * @param    {[type]}                 item [description]
 * @return   {[type]}                      [description]
 */
function binarySearch(data, item){
    var h = data.length - 1,
        l = 0;
    while(l <= h){
        var m = Math.floor((h + l) / 2);
        if(data[m] == item){
            return m;
        }
        if(item > data[m]){
            l = m + 1;
        }else{
            h = m - 1;
        }
    }
    // 返回false是没有找到该项
    return false;

    // 返回h是返回距离改项最近的前一项的索引号
    // return h
}
// 数组必须是有序数组
var arr=[-34,-12,-5,1,2,45,132,224];
binarySearch(arr,5);

JavaScript几种基本的算法