二分法查找 js 算法

二分法查找 js 算法

二分法查找算法：
采用二分法查找时，数据需是排好序的。
主要思想是：（设查找的数组区间为array[s, e]）
（1）确定该区间的中间位置m
（2）将查找的值T与array[m]比较,若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。
区域确定如下：
这里设array从小到大排列,
array[m]>T由数组的有序性可知array[m,……,e]>T;
故新的区间为array[s,……，m-1],
类似上面查找区间array[s,……，m-1]。
每一次查找与中间值比较，判断是否查找成功，不成功当前查找区间缩小一半，循环查找，即可。
时间复杂度:O(log2n)。

let arr = [0, 1, 2, 4, 5, 6, 7, 8];
let arr2 = [88, 77, 66, 55, 44, 33, 22, 11];

BinarySearch(arr2, 77);
BinarySearch(arr, 2);

function BinarySearch(arr, target) {
    let s = 0;
    let e = arr.length - 1;
    let m = Math.floor((s + e) / 2);
    let sortTag = arr[s] <= arr[e];//确定排序顺序

    while (s < e && arr[m] !== target) {
        if (arr[m] > target) {
            sortTag && (e = m - 1);
            !sortTag && (s = m + 1);
        } else {
            !sortTag && (e = m - 1);
            sortTag && (s = m + 1);
        }
        m = Math.floor((s + e) / 2);
    }

    if (arr[m] == target) {
        console.log('找到了,位置%s', m);
        return m;
    } else {
        console.log('没找到');
        return -1;
    }

}