Web＆MUSICブログ　QUALL

検索アルゴリズムのひとつ、二分探索(バイナリサーチ)を行うアルゴリズムをメモ。

<?php

class Search {

    /*
    * 二分探索を行う
    *
    * @return  探索値と一致する探索要素のキー、一致がなければNULL
    */
    function binarySearch($targetArr, $searchNum) {

        $low       = 0;
        $high      = count($targetArr) -1;

        while ($low < $high) {

            $mid = ($low + $high) / 2;

            if ($targetArr[$mid] == $searchNum) {
                return $mid;
            }

            if ($targetArr[$mid] < $searchNum) {
                $low  = $mid + 1;
            } else {
                $high = $mid;
            }
        }

        return NULL;
    }
}

    //検索値
    $searchNum    = 5;

    //検索対象要素
    $targetArr    = array(38, 72, 93, 41, 5, 18, 35, 86, 49, 17, 73, 782, 190);
    sort($targetArr);

    $mid = Search::binarySearch($targetArr, $searchNum);

    if ($mid === NULL) {
        echo "探索の該当はありません";
    } else {
        echo "探索結果は".$targetArr[$mid]."です";
    }

終わり。

関連記事

1. ページの短縮URLを貼り付けたTwitter投稿をしてもらう
2. CakePHP1.2上で外部サイトのRSSを取得＆表示[CakePHP]
3. 文字列を、1行上限★バイトで改行させて、上限★行まで表示する[PHP]
4. CakePHP1.2でRSS2.0を出力する[RSS][CakePHP]