A binary search on a sorted array.

test_searching_large_arrays.php

<?php

class Test_Searching_Large_Arrays extends PHPUnit_Framework_TestCase {

	const SAMPLE_SIZE = 100000;
	
	public function test_search()
	{
		$haystack = array();
		
		for ( $i = 0; $i < self::SAMPLE_SIZE; $i++ )
		{
			$haystack[] = substr( md5( rand() ), 0, 5);
		}

		sort( $haystack, SORT_STRING );

		$index = rand( 0, self::SAMPLE_SIZE );

		$needle = $haystack[$index];

		$this->assertTrue( in_array( $needle, $haystack ) );
		$this->assertTrue( $this->in_sorted_array( $needle, $haystack ) );
	}

	private function in_sorted_array( $needle, $haystack )
	{
		$min = 0;
		$max = count( $haystack ) - 1;
		
		while( $max >= $min )
		{
			$point = floor( ( $max + $min ) / 2 );

			$comparison = strcmp( $haystack[$point], $needle );

			switch ( true )
			{
				case $comparison < 0:
					$min = $point + 1;
					break;
				case $comparison > 0:
					$max = $point - 1;
					break;
				case $comparison == 0:
					return true;
					break;
			}
		
		}

		return false;
	}

}