← 都来码 / Dolaima← 例程索引typescript/school/binary_search.ts 原文

typescript/school/binary_search.ts · 721 字节 · 下载原文

// 二分查找 —— 经典算法练习(在有序数组里查目标)
// Binary search -- the classic algorithm exercise
//
// 来源 / Source: Rosetta Code「Binary search」JavaScript 条目(GFDL 1.2 / CC-BY-SA 3.0)

function binarySearch(items: number[], target: number): number {
    let low: number = 0;
    let high: number = items.length - 1;
    while (low <= high) {
        const mid: number = (low + high) >> 1;
        if (items[mid] === target) { return mid; }
        if (items[mid] < target) { low = mid + 1; }
        else { high = mid - 1; }
    }
    return -1;
}

const sorted: number[] = [1, 3, 5, 7, 9, 11, 13, 15];
println_int(binarySearch(sorted, 9));
println_int(binarySearch(sorted, 4));