BLOG ENTRY

PHPで二分探索(Binary Search)バイナリサーチのアルゴリズムのメモ

php

検索アルゴリズムのひとつ、二分探索(バイナリサーチ)を行うアルゴリズムをメモ。
[php]
<?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]."です";
}

[/php]

終わり。

WRITE COMMENT


(required)


(required)


(required)

MENU

veltica creative of twitter