使用 JavaScript 实现二分查找可视化

图形用户界面（GUI）相比单纯的程序代码，有助于我们更直观地理解算法的运行逻辑。在这篇文章中，我们将利用 JavaScript 来可视化二分查找算法。我们将看到在二分查找中，元素是如何被遍历的，直到找到给定的目标元素。我们还将通过可视化直观地理解二分查找的时间复杂度。

参考：

• JavaScript 中的异步函数

思路：

• 我们将使用不同的颜色来指示当前正在遍历的是哪个元素。
• 由于算法执行速度非常快，为了方便观察，我们使用了 setTimeout() 函数来减慢这个过程。
• 按下键盘上的“Ctrl+R”键可以生成一个新的随机数组。
• 核心的查找逻辑是通过 BinarySearch() 函数执行的。

示例：

下面是用于可视化二分查找的程序。

Filename: index.html

    
    
    


    

    
Binary Search
    

    


    

         Number to be Searched: 
        
        


        Search
        

        

        

    
    

Filename: style.css

* {
    margin: 0px;
    padding: 0px;
    box-sizing: border-box;
}

.header {
    font-size: 35px;
    text-align: center;
}

#array {
    background-color: white;
    height: 305px;
    width: 598px;
    margin: auto;
    position: relative;
    margin-top: 64px;
}

.block {
    width: 28px;
    background-color: #6b5b95;
    position: absolute;
    bottom: 0px;
    transition: 0.2s all ease;
}

.block_id {
    position: absolute;
    color: black;
    margin-top: -20px;
    width: 100%;
    text-align: center;
}

Filename: script.js

// JavaScript

var container = document.getElementById("array");

// Function to generate the array of blocks
function generatearray() {
    // Creating an array
    var arr = [];

    // Filling array with random values
    for (var i = 0; i < 20; i++) {
        // Return a value from 1 to 100 (both inclusive)
        var val = Number(Math.ceil(Math.random() * 100));
        arr.push(val);
    }

    // Sorting Array in ascending order
    arr.sort(function (a, b) {
        return a - b;
    });

    for (var i = 0; i < 20; i++) {
        var value = arr[i];

        // Creating element div
        var array_ele = document.createElement("div");

        // Adding class 'block' to div
        array_ele.classList.add("block");

        // Adding style to div
        array_ele.style.height = `${value * 3}px`;
        array_ele.style.transform = `translate(${i * 30}px)`;

        // Creating label element for displaying
        // size of particular block
        var array_ele_label = document.createElement("label");
        array_ele_label.classList.add("block_id");
        array_ele_label.innerText = value;

        // Appending created elements to index.html
        array_ele.appendChild(array_ele_label);
        container.appendChild(array_ele);
    }
}

// Asynchronous BinarySearch function
async function BinarySearch(delay = 300) {
    var blocks = document.querySelectorAll(".block");
    var output = document.getElementById("text");

    //Extracting the value of the element to be searched
    var num = document.getElementById("fname").value;

    //Colouring all the blocks violet
    for (var i = 0; i < blocks.length; i += 1) {
        blocks[i].style.backgroundColor = "#6b5b95";
    }

    output.innerText = "";

    // BinarySearch Algorithm
    var start = 0;
    var end = 19;
    var flag = 0;

    while (start 
            setTimeout(() => {
                resolve();
            }, delay)
        );

        //Current element is equal to the element
        //entered by the user
        if (value == num) {
            output.innerText = "Element Found";
            blocks[mid].style.backgroundColor = "#13CE66";
            flag = 1;
            break;
        }

        //Current element is greater than the element
        //entered by the user
        if (value > num) {
            end = mid - 1;
            blocks[mid].style.backgroundColor = "#6b5b95";
        } else {
            start = mid + 1;
            blocks[mid].style.backgroundColor = "#6b5b95";
        }
    }

    if (flag === 0) {
        output.innerText = "Element Not Found";
    }
}

// Calling generatearray function
generatearray();

输出效果：

屏幕上会出现一组排序好的柱状图，通过输入数字并点击搜索，我们可以观察到算法如何通过二分法快速锁定目标位置，红色代表当前比较的中间元素，绿色代表匹配成功。