品易云推流 关闭
文章详情页
文章 > JavaScript > JavaScript二分查找算法的使用

JavaScript二分查找算法的使用

JavaScript二分查找

头像

小妮浅浅

2021-08-19 16:47:331836浏览 · 0收藏 · 0评论

说明

1、使用二分查找算法查找数组中相应的目标值下标。

2、二分搜索算法的前提是一个有序的数组,所以当编码实现时,首先要对其进行排序。

二分查找的过程

(1)分成两半,最左边的指针low,最右边的指针high,最中间的指针mid。

(2)如果找到的目标值小于中间mid对应的值,则表示目标值在左边,则缩小范围,将high设置为mid-1。

(3)如果找到的目标值大于中间mid对应的值,则表示目标值在右边,则缩小范围,将low设置为mid+1。

(4)如果找到的目标值等于中间mid对应的值,则直接返回mid。

实例

Array.prototype.binarySort = function(target) {
    // 随便用什么算法排,但是二分查找的前提是有序数组哦
    this.quickSort();
    let low = 0;
    let high = this.length - 1;
    while(low <= high) {
        const mid = Math.floor((low + high) /2);
        const midItem = this[mid];
        // 如果查找的目标值小于中间的点
        if(target < midItem ) {
            // 说明目标值在左半边,那high指针就是mid的前一位
            high = mid - 1;
        } else if(target > midItem) {
            // 如果目标值在右半边,那low指针就是mid的后面一位
            low = mid + 1;
        } else {
            // 目标值就是正中间
            return mid;
        }
    }
    // 没找到
    return -1;
}
 
const arr = [1, 5, 9, 3, 18, 6, 2, 7]
console.log(arr.binarySort(9));

以上就是JavaScript二分查找算法的使用,希望对大家有所帮助。更多Javascript学习指路:Javascript

推荐操作环境:windows7系统、jquery3.2.1版本,DELL G3电脑。

关注

关注公众号,随时随地在线学习

本教程部分素材来源于网络,版权问题联系站长!

底部广告图