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));