本文主要介绍了web前端入门到精通--JavaScript实现二分查找（搜索）算法（非递归实现） ，通过具体的内容向大家展现，希望对大家前端开发Javascript的学习有所帮助。

JavaScript实现前端经典算法二分查找，面试常考哟~

一、二分查找算法分析

用二分查找算法查找目标值在数组中对应的下标

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实现快速排序算法

Array.prototype.quickSort = function() {

    const rec = (arr) => {

        if(arr.length <= 1) return arr;

        const base = arr[0];

        const left = [];

        const right = [];

        for(let i = 1; i < arr.length; i += 1) {

            if(arr[i] < base) {

                left.push(arr[i]);

            } else {

                right.push(arr[i]);

            }

        }

        return [...rec(left), base, ...rec(right)];

    }

    const res = rec(this);

    res.forEach((item, key) => {

        this[key] = item;

    });

}

三、时间复杂度

对半劈递归的是O(logn)，这种对半劈一层循环的也是O(logn)

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评