a blog by Christian Snodgrass
about programming, web and game design, and everything else

Keep It Sorted: Binary Search Sort

In a previous article, I discussed binary searching and mentioned that you could modify the function a bit to get the index of where to put the value to keep it sorted. This eliminates the need to sort it on demand and lose all the performance gains of the binary search.

The Binary Search Sort Function

ActionScript 3

public function InverseBinarySearch(values:Array, target:*, min:int, max:int):int { 
    var mid:int = Math.floor((min + max) / 2); 
			 
    if (values.length == 0) 
        return 0; 
				 
    if (min > max) { 
        return min; 
    } else if (max == min) { 
        if (mid < values.length && target == values[mid]) 
            return -1; 
        if(mid >= values.length || target < values[mid]) 
            return max; 
        return max + 1; 
			 
    if (target > values[mid]) 
        return InverseBinarySearch(values, target, mid + 1, max); 
    else if (target < values[mid]) 
        return InverseBinarySearch(values, target, min, mid - 1); 
    return -1; 

Javascript

function InverseBinarySearch(values, target, min, max) { 
    var mid = Math.floor((min + max) / 2); 
			 
    if (values.length == 0) 
        return 0; 
				 
    if (min > max) { 
        return min; 
    } else if (max == min) { 
        if (mid < values.length && target == values[mid]) 
            return -1; 
        if(mid >= values.length || target < values[mid]) 
            return max; 
        return max + 1; 
			 
    if (target > values[mid]) 
        return InverseBinarySearch(values, target, mid + 1, max); 
    else if (target < values[mid]) 
        return InverseBinarySearch(values, target, min, mid - 1); 
    return -1; 

PHP

function InverseBinarySearch($values, $target, $min, $max) { 
    $mid = floor(($min + $max) / 2); 
			 
    if (count($values) == 0) 
        return 0; 
				 
    if ($min > $max) { 
        return $min; 
    } else if ($max == $min) { 
        if ($mid < count($values) && $target == $values[$mid]) 
            return -1; 
        if($mid >= count($values) || $target < $values[mid]) 
            return $max; 
        return $max + 1; 
			 
    if ($target > $values[mid]) 
        return InverseBinarySearch($values, $target, $mid + 1, $max); 
    else if ($target < $values[mid]) 
        return InverseBinarySearch($values, $target, $min, $mid - 1); 
    return -1; 

Using the Binary Search Sort Function

Using the function is pretty straightforward. Instead of doing a normal push into the array, you use the function to figure out the index. Then, if the index is greater than -1, you use the splice function to add the value.

ActionScript 3

// @return true if it was added, false if it wasn't. 
public function AddValue(values:Array, value:*):Boolean { 
    var index:int = InverseBinarySearch(values, value, 0, values.length - 1); 
 
    if(index == -1) 
        return false; 
 
    values.splice(index, 0, value); 
    return true; 

Javascript

// @return true if it was added, false if it wasn't. 
function AddValue(values, value) { 
    var index = InverseBinarySearch(values, value, 0, values.length - 1); 
 
    if(index == -1) 
        return false; 
 
    values.splice(index, 0, value); 
    return true; 

PHP

// @return true if it was added, false if it wasn't. 
function AddValue($values, $value) { 
    $index = InverseBinarySearch($values, $value, 0, count($values) - 1); 
 
    if($index == -1) 
        return false; 
 
    array_splice($values, $index, 0, $value); 
    return true; 

How It Works

The idea is simple. Most of it is the same as the traditional binary search. The only different part is what we do when we find the spot. Normally we return the index we’re at and we’re done.

This time we have a bit more to do. We have to compare our values and figure out if we’re at the index we want, above or below it.

Unique or Duplicates Allowed

The other consideration we have to take into account is whether or not we want to allow duplicates. In the above, it doesn’t. If it finds the value already there, it returns -1.

If you want to allow duplicates, you could simpy replace the -1 with the max value.

Or, better yet, make it an optional parameter in your function. And without further ado…

The Binary Search Sort Function, version 2

ActionScript 3

public function InverseBinarySearch(values:Array, target:*, min:int, max:int, allowDup:Boolean = false):int { 
    var mid:int = Math.floor((min + max) / 2); 
			 
    if (values.length == 0) 
        return 0; 
				 
    if (min > max) { 
        return min; 
    } else if (max == min) { 
        if (mid < values.length) && target == values[mid]) 
            return (allowDup ? mid : -1); 
        if(mid >= values.length || target < values[mid]) 
            return max; 
        return max + 1; 
			 
    if (target > values[mid]) 
        return InverseBinarySearch(values, target, mid + 1, max); 
    else if (target < values[mid]) 
        return InverseBinarySearch(values, target, min, mid - 1); 
    return -1; 

Javascript

function InverseBinarySearch(values, target, min, max, allowDup) { 
    if(typeof allowDup == 'undefined') 
        allowDup = false; 
 
    var mid = Math.floor((min + max) / 2); 
			 
    if (values.length == 0) 
        return 0; 
				 
    if (min > max) { 
        return min; 
    } else if (max == min) { 
        if (mid < values.length && target == values[mid]) 
            return (allowDup ? mid : -1); 
        if(mid >= values.length || target < values[mid]) 
            return max; 
        return max + 1; 
			 
    if (target > values[mid]) 
        return InverseBinarySearch(values, target, mid + 1, max); 
    else if (target < values[mid]) 
        return InverseBinarySearch(values, target, min, mid - 1); 
    return -1; 

PHP

function InverseBinarySearch($values, $target, $min, $max, $allowDup = false) { 
    $mid = floor(($min + $max) / 2); 
			 
    if (count($values) == 0) 
        return 0; 
				 
    if ($min > $max) { 
        return $min; 
    } else if ($max == $min) { 
        if ($mid < count($values) && $target == $values[$mid]) 
            return ($allowDup ? $mid : -1); 
        if($mid >= count($values) || $target < $values[mid]) 
            return $max; 
        return $max + 1; 
			 
    if ($target > $values[mid]) 
        return InverseBinarySearch($values, $target, $mid + 1, $max); 
    else if ($target < $values[mid]) 
        return InverseBinarySearch($values, $target, $min, $mid - 1); 
    return -1; 

Using the Improved Function

If you didn’t notice the changes, all we did was add an optional parameter (allowDup) and modified one of the returns to return mid instead of -1 if allowDup is true.

Using the improved function is almost identical to the previous method. The only difference is you can optionally pass true, which will cause it to always return a valid index to insert. If using true you can even remove the check for -1 (though it doesn’t hurt much to leave it).

If there is a duplicate value, it doesn’t matter which side you put the duplicate, as long as it’s right next to it, thus we can just return the position of that duplicate value. Easy, huh?

These functions allow you to make use of the crazy efficiency of binary search, while also harnessing that power for keeping the array sorted.


Related Articles


Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Back to Top