Skip to content

Instantly share code, notes, and snippets.

@acairns
Last active December 24, 2015 00:49
Show Gist options
  • Save acairns/6719700 to your computer and use it in GitHub Desktop.
Save acairns/6719700 to your computer and use it in GitHub Desktop.
A binary search on a sorted array.
<?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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment