JS二分法寻找数组元素

var arr = [3, 5, 9, 12, 18, 35, 45, 50, 62, 68, 79, 93];
function searching(target) {
    // start   开始位置
    // end     结束位置
    // middle  中间位置
    // ele     中间的元素
    var start = 0, end = arr.length - 1, middle, ele;
    while (start <= target) {
        middle = Math.floor((start + end) / 2);
        ele = arr[middle];
        if (ele == target) {
            return middle
        } else if (target < ele) {
            end = middle - 1
        } else if(target > ele) {
            start = middle + 1
        }
    } 
    return -1;
}
console.log(searching(12));  // 3

先找到中间的元素做对比。当传入的值小于中间值时候(此时的区间为start-middle),将end修改为middle-1位(这个时候就是start-middle的区间)。当传入的值大于中间值的时候(此时区间为middle-end),将start修改为middle+1位(这个时候就是middle-end的区间),以此反复循环,直到传入的值就是middle。

发表评论

电子邮件地址不会被公开。 必填项已用*标注