二分検索

そのまま書き下してみましたけど、ランダムでサンプルを発生させたらヒットしないものですね。(苦笑)

• 404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)

#! /usr/bin/gawk -f
# bin_search.awk - binary search
#   input:  min, max
#   output: result of binary search

BEGIN {
    srand();
    for (i = 1; i <= 1000; i++) {
        array[i] = int(rand() * 100);
    }
    print binary_search(array, 50, 1, 100);
}

function binary_search(array, value, head, tail) {
    if (head > tail) {
        return -1;
    }
    where = int((head + tail) / 2);
    if (value == array[where]) {
        return where;
    }
    if (value < array[where]) {
        tail = where - 1;
    } else {
        head = where + 1;
    }
    return binary_search(array, value, head, tail);
}