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