BLOG ENTRY

previousnext

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

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

  1. <?php
  2.  
  3. class Search {
  4.  
  5.     /*
  6.     * 二分探索を行う
  7.     *
  8.     * @return  探索値と一致する探索要素のキー、一致がなければNULL
  9.     */
  10.     function binarySearch($targetArr, $searchNum) {
  11.  
  12.         $low       = 0;
  13.         $high      = count($targetArr) -1;
  14.  
  15.         while ($low <$high) {
  16.  
  17.             $mid = ($low + $high) / 2;
  18.  
  19.             if ($targetArr[$mid] == $searchNum) {
  20.                 return $mid;
  21.             }
  22.  
  23.             if ($targetArr[$mid] <$searchNum) {
  24.                 $low  = $mid + 1;
  25.             } else {
  26.                 $high = $mid;
  27.             }
  28.         }
  29.  
  30.         return NULL;
  31.     }
  32. }
  33.  
  34.     //検索値
  35.     $searchNum    = 5;
  36.  
  37.     //検索対象要素
  38.     $targetArr    = array(38, 72, 93, 41, 5, 18, 35, 86, 49, 17, 73, 782, 190);
  39.     sort($targetArr);
  40.  
  41.     $mid = Search::binarySearch($targetArr, $searchNum);
  42.  
  43.     if ($mid === NULL) {
  44.         echo "探索の該当はありません";
  45.     } else {
  46.         echo "探索結果は".$targetArr[$mid]."です";
  47.     }



終わり。

comments(0)
はてなブックマークに追加 del.icio.usに追加 ライブドアクリップに追加 POOKMARK Airlinesに追加 Buzzurl（バザール）に追加 ニフティクリップに追加
DATE2008.05.13

WRITE COMMENT


（required）


（required）


（required）

MENU