← 都来码 / Dolaima← 例程索引javascript/school/binary_search.js 原文

javascript/school/binary_search.js · 1088 字节 · 下载原文

// 二分查找 —— 经典查找练习(在升序数组里找一个值,返回下标)
// Binary search -- the classic search exercise (find a value in a sorted array, return its index)
//
// 来源 / Source: Rosetta Code「Binary search」JavaScript 条目(GFDL 1.2 / CC-BY-SA 3.0)
//   https://rosettacode.org/wiki/Binary_search
// 改编 / Adapted: 输出由 return 改为本平台的 println_int(找不到时打 -1)。
//   Output changed to this platform's println_int (-1 when not found).

function binary_search_iterative(a, value) {
    var mid, lo = 0,
        hi = a.length - 1;

    while (lo <= hi) {
        mid = Math.floor((lo + hi) / 2);

        if (a[mid] > value) {
            hi = mid - 1;
        } else if (a[mid] < value) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

var arr = [1, 3, 5, 7, 9, 11, 13, 15];

println_int(binary_search_iterative(arr, 1));
println_int(binary_search_iterative(arr, 7));
println_int(binary_search_iterative(arr, 15));
println_int(binary_search_iterative(arr, 4));