note 89413 added to function.array-search

As others have noted, if your array is already sorted, a binary search is the way to go. When I realized PHP doesn't have a native one, I came here to see what others had done to implement this workhorse algorithm. While I appreciate those that have posted their own solutions here, none of those implementations met my needs. Also, due mainly to non-optimal loop processing, the code offered required extra post-processing to handle various ways the search loop may have exited. Proper coding of initial conditions and the main loop eliminates this extra processing. Also, the solutions presented assumed a simple one-dimensional array and basic comparisons. I needed to search an array of user objects, with the comparison performed on one of the object attributes. C/C++ handles the need for comparison flexibility by the binary search function taking a parameter that points to a user function that performs any arbitrarily complex comparison and returns a defined result depending on the relative magnitudes of the compared entities. Since PHP allows similar function reference parameters, I realised it would be quite easy to implement this functionality. I won't go into an explanation of the algorithm chosen for the main binary search function, google "binary searches" if you don't understand how they work. I will mention however that the ONLY way to exit the main loop in this function is on a match, or a definite fail. The loop will never terminate while the result of the search is indeterminate. Some solutions I've seen here and elsewhere return the index of the found element on a match, and "false" on a fail. Since PHP treats a zero the same as false in expressions, and zero is a valid array index, using false to designate "not found" gives an ambiguous result in some cases. I chose to use the value -1 to signify a search failure instead. <?php function array_bsearch( $needle, $haystack, $comparator ) { $high = Count( $haystack ) -1; $low = 0; while ( $high >= $low ){ $probe = Floor( ( $high + $low ) / 2 ); $comparison = $comparator( $haystack[$probe], $needle ); if ( $comparison < 0 ) { $low = $probe +1; } elseif ( $comparison > 0 ) { $high = $probe -1; } else { return $probe; } } // ---The loop ended without a match return -1; } ?> In this function the parameters "$needle" and "$haystack" have the same meaning as for the native array_search() PHP function. The third parameter, "$comparator" is the name of the function to use to determine if an array element matches the needle. The array_bsearch() function is self-contained, and doesn't need modification no matter how complex the comparison needs to be. The actual comparison is performed by a purpose-written user function that takes two parameters and returns a numerical result. array_bsearch() will call this function each time it needs to compare an array element to the needle. The first parameter passed will be the element to test, and the second will the the needle value passed to array_bsearch(). Note that if you will always search for the same thing your user function can ignore the second parameter and hard-code the test on the first parameter. The comparison user function must return a positive number if the element is greater than the needle, a negative number if it is smaller than the needle, and zero if they match. Given a scenario where you want to find the index of a user object loaded from MySQL in an array, where the "my_key" property equals 54. Here's how you could code it using a user function and the new array_bsearch() function. <?php function KeyCompare( $obj, $needle ) { if ( $obj['my_key'] < $needle ) { return -1; } elseif ( $obj['my_key'] > $needle ) { return 1; } else { return 0; } } $index = array_bsearch( 54, $my_array, 'KeyCompare' ); ?> Hope this is helpful to somebody out there. ---- Server IP: 216.235.13.26 Probable Submitter: 69.196.166.240 ---- Manual Page -- http://www.php.net/manual/en/function.array-search.php Edit -- https://master.php.net/note/edit/89413 Del: integrated -- https://master.php.net/note/delete/89413/integrated Del: useless -- https://master.php.net/note/delete/89413/useless Del: bad code -- https://master.php.net/note/delete/89413/bad+code Del: spam -- https://master.php.net/note/delete/89413/spam Del: non-english -- https://master.php.net/note/delete/89413/non-english Del: in docs -- https://master.php.net/note/delete/89413/in+docs Del: other reasons-- https://master.php.net/note/delete/89413 Reject -- https://master.php.net/note/reject/89413 Search -- https://master.php.net/manage/user-notes.php