# Binary search algorithm for non-overlapping time spans and possible gaps

I have a data structure, containing time span nodes, with the following properties:

• Nodes are sorted ascending
• Time spans will not overlap, but may have gaps between them
• Each node will have a start datetime and a finish datetime
• The last node's finish may also be null (not finished yet)

I want to be able to find the node that intersects a given datetime, or return false if no match is found — basically resembling the following sql query for a sql table with similar properties as my data structure:

SELECT t.*
FROM table t
WHERE t.start <= @probeDate AND
( t.finish >= @probeDate OR
t.finish IS NULL )


I've concluded that a (variation of a) binary search is probably the most efficient search algorithm. So, this is what I have come up with so far:

<?php
class Node
{
protected $start; protected$finish;

public function __construct( DateTime $start, DateTime$finish = null )
{
$this->start =$start;
$this->finish =$finish;
}

public function getStart()
{
return $this->start; } public function getFinish() { return$this->finish;
}

public function __toString()
{
/* for easy displaying of the timespan */
return $this->start->format( 'H:i:s' ) . ' - ' . ( null !==$this->finish ? $this->finish->format( 'H:i:s' ) : '∞' ); } } class NodeList { protected$nodes;

public function __construct( array $nodes = array() ) {$this->nodes = $nodes; } public function find( DateTime$date )
{
$min = 0;$max = count( $this->nodes ) - 1; return$this->binarySearch( $date,$min, $max ); } protected function binarySearch($date, $min,$max )
{
if( $max <$min )
{
return false;
}
else
{
$mid = floor($min + ( ( $max -$min ) / 2 ) );
$node =$this->nodes[ $mid ];$start  = $node->getStart();$finish = $node->getFinish(); if($date < $start ) { return$this->binarySearch( $date,$min, $mid - 1 ); } else if($date > $finish ) { if($finish == null )
{
return $node; } else { return$this->binarySearch( $date,$mid + 1, $max ); } } else { return$node;
}
}
}
}


I am testing it with the following:

$nodes = array( new Node( new DateTime( '01:01:00' ), new DateTime( '01:05:00' ) ), new Node( new DateTime( '01:06:00' ), new DateTime( '01:10:00' ) ), new Node( new DateTime( '01:11:00' ), new DateTime( '01:15:00' ) ), new Node( new DateTime( '01:16:00' ), new DateTime( '01:20:00' ) ), new Node( new DateTime( '01:21:00' ), new DateTime( '01:25:00' ) ), new Node( new DateTime( '01:26:00' ), new DateTime( '01:30:00' ) ), new Node( new DateTime( '01:31:00' ), new DateTime( '01:35:00' ) ), new Node( new DateTime( '01:36:00' ), new DateTime( '01:40:00' ) ), new Node( new DateTime( '01:41:00' ) ) );$list = new NodeList( $nodes );$date = new DateTime( '01:00:00' );
for( $i = 0;$i < 100; $i++,$date->modify( '+30 seconds' ) )
{
$node =$list->find( $date ); echo 'find: ' .$date->format( 'H:i:s' ) . PHP_EOL;
echo ( $node !== false ? (string)$node : 'false' ) . PHP_EOL . PHP_EOL;
}


Do you see any inherent flaws and/or ways to improve this algorithm? Perhaps you even know of a more time efficient algorithm to accomplish the same?

PS.: Don't worry about the internal integrity of NodeList and Node (checking for invalid nodes, invalid min and max datetimes, checking overlaps, etc.) — this is just a quick and dirty concept. I'm primarily interested in the search algorithm in NodeList::find() and consequently NodeList::binarySearch().

-
You will probably get better luck with algorithms on either SO or Programmers.SO. This site is more geared towards code review, not algorithm review. I wish I could help more, but I was absolutely terrible when I took algorithms. Best of luck –  mseancole Dec 26 '12 at 14:52