メニュー
ブログ更新履歴
コンテンツ更新履歴
リンク
  • Magome
  • クラウドベースのMIDIシーケンサ
    音楽制作に興味のある方を対象に、スタンドアロンでも使え、ネットならではの面白さも兼ね備えた音楽制作アプリの提供を目指しています。
twitter

PHP には何故か二分探索(バイナリサーチ)が標準で用意されてません。
PHPにとってあまり重要ではないのか?言語的に別の手段で解決できるものなのか?というような事情はわかってはいませんが、あれば便利だと思うので作ってみました。

  • 配列内にお目当ての要素があるか否かだけの関数(いわゆる C++ で言う std::binary_search )だけでなく、
    最初に現れた指定値以上の要素の位置を返す関数( std::lower_bound )と、
    最初に現れた指定値を超えた要素の位置を返す関数( std::upper_bound )を用意してます。
    きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。
  • 単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。
  • 配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。
    もちろん、正しくソートされてない配列の場合の結果は不定です。

クラス定義 anchor.png

<?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] );
	}

}
Page Top

サンプルコード anchor.png

// サンプルコード
$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

Front page   Freeze Diff Backup Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help   RSS of recent changes (RSS 1.0) RSS of recent changes (RSS 2.0) RSS of recent changes (RSS Atom) Powered by xpWiki
Counter: 1823, today: 2, yesterday: 3
Princeps date: 2016-04-21 (Thu) 15:37:58
Last-modified: 2016-04-21 (Thu) 15:37:58 (JST) (1276d) by takatsuka