JS实现二分查找算法

FireDragonZL commented 4 years ago

[x] 要求：
什么是二分查找算法？以及他的适用场景。
使用 JavaScript 实现二分查找算法

FireDragonZL commented 4 years ago

[x] 二分查找：又称折半查找。比较次数少，查找速度快，平均性能高。较基本查找相比效率要高很多。但前提是：数组有序。

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>二分查找算法实现：返回目标数字的索引位置</title>
</head>
<body>
<script>
    // 以升序数组为例
    var data = [2,5,6,9,11,13,16,18,21,26,58,100];
    const target = 10;

    binarySelect(data, target);

    // 二分查找函数
    function binarySelect(array, target){
        var left = 0;
        var right = array.length - 1;
        var middle = 0;
        while (left <= right) {
            // 向下取整
            middle = Math.floor((left + right) / 2);
            if (array[middle] === target) {
                console.log("目标值索引为：" + middle);
                // return只在函数体中有效
                return "目标值索引为：" + middle;
            } else if (array[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        console.log("数组不包含该目标值");
        return -1;
    }
</script>
</body>
</html>

lurasso commented 4 years ago

function binarySerch(data,dset,start,end){
            var end = end || data.length - 1,
                start = start || 0,
                m = Math.floor((start+end)/2);
            if(data[m]==dset){
                return m;
            }
            if(dset<data[m]){
                return binarySerch(data,dset,0,m-1);
            }else{
                return binarySerch(data,dset,m+1,end);
            }
            return false;
        }
        var arr = [-10 , -4 , 0 , 1 , 5 , 7 , 16 , 18 ,30]
        console.log(binarySerch(arr,7));  //5

748580573 commented 4 years ago

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>冒泡</title>
</head>

<body>
    <div class="circle1"></div>
    <div class="circle2"></div>
    <div class="circle3"></div>
</body>

<script>
    var data = [2, 5, 6, 9, 11, 13, 16, 18, 21, 26, 58, 100];
    const target = 10;
    binarySelect(data, 100);
    function binarySelect(array,target){
        var left = 0;
        var right = data.length - 1;
        var middle = 0;
        for(;right >= 0 && left <= data.length - 1;){
            middle = Math.floor((left + right) / 2);
            if(target > array[middle]){
                left = middle + 1;
            }else if(target < array[middle]){
                right = middle - 1;
            }else{
                console.log(middle);
                break;
            }
        }
    }
</script>

</html>

FireDragonZL commented 4 years ago

for (; right >= 0 && left <= data.length - 1;) 这种可以改成while循环

goldEli / Front-End-Training

JS实现二分查找算法 #41