Binary search: comparing Java to PHP performance


Binary search finds the specified key in a given sorted array, then returns it’s position. The algorithm runs in:

worst case: O(log n)
best case: O(1)
average: O(log n)


In the debate of Java vs PHP it was asked why use java when many tasks require less code in PHP. The answer while complex boils down to performance. This is a tiny example to show a performance comparison for each language.

The Algorithms

As a additional angle I have added two separate implementations of the binary search in Java. One will use arrayLists while the other integer array. Additionally, JDK 7 / 8 will ran separately to analyze platform performance.

public static int binarySearch(ArrayList<Integer> array, int key) {

        int position, lower = 0, upper = array.size() - 1;

        // To start, find the subscript of the middle position.
        position = (lower + upper) / 2;

        while ((array.get(position) != key) && (lower <= upper)) {
            if (array.get(position) > key) {
                upper = position - 1;
            } else {
                lower = position + 1;
            position = (lower + upper) / 2;

        return ((lower <= upper) ? position : -1);

The PHP implementation uses a straight integer array.

public function binary_search($a, $key) {

	$lo = 0;
	$hi = sizeof($a) - 1;
	$position = (int)(($lo + $hi) / 2);
	while (($a[$position] != $key) && ($lo <= $hi)) {
		if ($a[$position] > $key) {
			$hi = $position - 1;
		} else {
			$lo = $position + 1;

		$position = (int)(($lo + $hi) / 2);

	unset($a, $key);
	return (($lo <= $hi) ? $position : -1);

Each algorithm fed in X number of presorted ints. For java to assure accuracy 50 iterations on the algorithm is performed to determine the run time. PHP is configured for 10 iterations due to the memory limit of 2 gigabytes.


[visualizer id=”394″]


Java 7 / 8 performance does not differ. An arrayList in has slightly more overhead compared to a pure integer array. As expected PHP performance is considerable worse that Java. PHP is not designed to hold 10 million ints in memory. To make this test work, the memory allocated to php had to be adjusted to 2gb. In conclusion, leave the large data sets to integer arrays in Java, not PHP to have the best performance.

To run your own tests checkout either the PHP or Java repository on Github.

Tech Specs
Java JDK 8 / 7
PHP 5.5 (2GB memory allocated)
AMD FX 8-core
16gb RAM 1600mhz