|
Cur: 2016-04-21 (Thu) 15:37:58 takatsuka  |
| | + | #contents |
| | + | PHP には何故か二分探索(バイナリサーチ)が標準で用意されてません。 |
| | + | PHPにとってあまり重要ではないのか？言語的に別の手段で解決できるものなのか？というような事情はわかってはいませんが、あれば便利だと思うので作ってみました。 |
| | | | |
| | + | -配列内にお目当ての要素があるか否かだけの関数（いわゆる C++ で言う std::binary_search ）だけでなく、 |
| | + | 最初に現れた指定値以上の要素の位置を返す関数（ std::lower_bound ）と、 |
| | + | 最初に現れた指定値を超えた要素の位置を返す関数（ std::upper_bound ）を用意してます。 |
| | + | きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。 |
| | + | |
| | + | -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。 |
| | + | |
| | + | -配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。 |
| | + | もちろん、正しくソートされてない配列の場合の結果は不定です。 |
| | + | |
| | + | ***クラス定義 [#t3b1a0db] |
| | + | #prettify{{ |
| | + | <?php |
| | + | |
| | + | class CBinarySearch |
| | + | { |
| | + | // std::upper_bound 普通の配列専用版 |
| | + | public static function UpperBound( $list, $value ) |
| | + | { |
| | + | return self::UpperBoundT( $list, $value, |
| | + | function( $value, $elem ){ |
| | + | return $value < $elem; |
| | + | }); |
| | + | } |
| | + | |
| | + | // std::upper_bound 自前比較関数を渡す版 |
| | + | public static function UpperBoundT( $list, $value, $funcLess ) |
| | + | { |
| | + | $count = count($list); |
| | + | $first = 0; |
| | + | while( 0 < $count ){ |
| | + | $count2 = (int)($count / 2); |
| | + | $mid = $first + $count2; |
| | + | if( ! $funcLess( $value, $list[$mid] ) ){ |
| | + | $first = ++$mid; |
| | + | $count -= $count2 + 1; |
| | + | }else{ |
| | + | $count = $count2; |
| | + | } |
| | + | } |
| | + | return $first; |
| | + | } |
| | + | |
| | + | // std::lower_bound 普通の配列専用版 |
| | + | public static function LowerBound( $list, $value ) |
| | + | { |
| | + | return self::LowerBoundT( $list, $value, |
| | + | function( $elem, $value ){ |
| | + | return $elem < $value; |
| | + | }); |
| | + | } |
| | + | |
| | + | // std::lower_bound 自前比較関数を渡す版 |
| | + | public static function LowerBoundT( $list, $value, $funcLess ) |
| | + | { |
| | + | $count = count($list); |
| | + | $first = 0; |
| | + | while( 0 < $count ){ |
| | + | $count2 = (int)($count / 2); |
| | + | $mid = $first + $count2; |
| | + | if( $funcLess( $list[$mid], $value ) ){ |
| | + | $first = ++$mid; |
| | + | $count -= $count2 + 1; |
| | + | }else{ |
| | + | $count = $count2; |
| | + | } |
| | + | } |
| | + | return $first; |
| | + | } |
| | + | |
| | + | // std::binary_search 普通の配列専用版 |
| | + | public static function BinarySearch( $list, $value ) |
| | + | { |
| | + | $f = function( $elem, $value ){ |
| | + | return $elem < $value; |
| | + | }; |
| | + | return self::BinarySearchT( $list, $value, $f, $f ); |
| | + | } |
| | + | |
| | + | // std::binary_search 自前比較関数を渡す版 |
| | + | public static function BinarySearchT( $list, $value, $funcLess0, $funcLess1 ) |
| | + | { |
| | + | $first = self::LowerBoundT($list, $value, $funcLess0 ); |
| | + | return $first>=count($list) ? false : ! $funcLess1( $value, $list[$first] ); |
| | + | } |
| | + | |
| | + | } |
| | + | }} |
| | + | ***サンプルコード [#j2930aa3] |
| | + | #prettify{{ |
| | + | // サンプルコード |
| | + | $list = [-5, 0, 5, 10, 10, 11, 11, 13, 18]; // ソート済みの配列 |
| | + | $testValues = [-7, -5, 0, 1, 2, 10, 12, 13, 18, 19 ]; // テストケース |
| | + | |
| | + | echo '<br>LowerBound'; |
| | + | foreach( $testValues as $v ){ |
| | + | echo " {$v}:" . CBinarySearch::LowerBound($list,$v); // 結果表示 |
| | + | } |
| | + | |
| | + | echo '<br>UpperBound'; |
| | + | foreach( $testValues as $v ){ |
| | + | echo " {$v}:" . CBinarySearch::UpperBound($list,$v); // 結果表示 |
| | + | } |
| | + | |
| | + | echo '<br>BinarySearch'; |
| | + | foreach( $testValues as $v ){ |
| | + | echo " {$v}:" . ( CBinarySearch::BinarySearch($list,$v) ? '1' : '0' ); // 結果表示 |
| | + | } |
| | + | |
| | + | // 自前比較関数版 |
| | + | echo '<br>BinarySearchT'; |
| | + | foreach( $list as $v ){ // サンプルデータの作成 |
| | + | $list2[] = [ 'id' => $v ]; |
| | + | } |
| | + | foreach( $testValues as $v ){ |
| | + | $less0 = function( $elem, $value ){ // 引数の型違いの関数は別々の関数にするしかない。 |
| | + | return $elem['id'] < $value; // ちょっと冗長っぽいかもだけど、 |
| | + | }; // 致し方ない。 |
| | + | $less1 = function( $value, $elem ){ // もう少しスマートな書き方があるなら、 |
| | + | return $value < $elem['id']; // 教えてほしいです。 |
| | + | }; |
| | + | echo " {$v}:" . ( CBinarySearch::BinarySearchT($list2,$v,$less0,$less1) ? '1' : '0' ); // 結果表示 |
| | + | } |
| | + | }} |
| | + | |
| | + | サンプルコードの結果は以下です。 |
| | + | LowerBound -7:0 -5:0 0:1 1:2 2:2 10:3 12:7 13:7 18:8 19:9 |
| | + | UpperBound -7:0 -5:1 0:2 1:2 2:2 10:5 12:7 13:8 18:9 19:9 |
| | + | BinarySearch -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 19:0 |
| | + | BinarySearchT -7:0 -5:1 0:1 1:0 2:0 10:1 12:0 13:1 18:1 19:0 |
Back to page
