技術系備忘録​/PHP​/二分探索(binary search) :: シンクリッジ

クラス定義 ^[1]

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

}

サンプルコード ^[2]

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