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 &lt;= @probeDate AND
    ( t.finish &gt;= @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:

&lt;?php
class Node
{
    protected $start;
    protected $finish;

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

    public function getStart()
    {
        return $this-&gt;start;
    }

    public function getFinish()
    {
        return $this-&gt;finish;
    }

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

class NodeList
{
    protected $nodes;

    public function __construct( array $nodes = array() )
    {
        $this-&gt;nodes = $nodes;
    }

    public function find( DateTime $date )
    {
        $min = 0;
        $max = count( $this-&gt;nodes ) - 1;

        return $this-&gt;binarySearch( $date, $min, $max );
    }

    protected function binarySearch( $date, $min, $max )
    {
        if( $max &lt; $min )
        {
            return false;
        }
        else
        {
            $mid = floor( $min + ( ( $max - $min ) / 2 ) );    
            $node   = $this-&gt;nodes[ $mid ];
            $start  = $node-&gt;getStart();
            $finish = $node-&gt;getFinish();
            if( $date &lt; $start )
            {
                return $this-&gt;binarySearch( $date, $min, $mid - 1 );
            }
            else if( $date &gt; $finish )
            {
                if( $finish == null )
                {
                    return $node;
                }
                else
                {
                    return $this-&gt;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 &lt; 100; $i++, $date-&gt;modify( '+30 seconds' ) )
{
    $node = $list-&gt;find( $date );
    echo 'find: ' . $date-&gt;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().
Flatter code is less arrow-shaped

In cases like this:


if( $max &lt; $min )
{
    return false;
}
else
{
    // more deeply nested conditions ...
}



When the if branch ends with a return statement,
you can eliminate the else branch,
making the code flatter and less arrow-shaped,
which often makes it easier to read:

if( $max &lt; $min )
{
    return false;
}

// more code ...


Fishy comparison

Although this is apparently valid PHP, comparing a date against a null value using the &gt; operator seems like a dirty hack:


else if( $date &gt; $finish )
{
    if( $finish == null )



I would reorganize the conditions in that piece of code:

if( $max &lt; $min )
{
    return false;
}

$mid = floor( $min + ( ( $max - $min ) / 2 ) );    
$node   = $this-&gt;nodes[ $mid ];
$start  = $node-&gt;getStart();
$finish = $node-&gt;getFinish();

if( $date &lt; $start )
{
    return $this-&gt;binarySearch( $date, $min, $mid - 1 );
}

if( $finish == null )
{
    return $node;
}

if( $date &gt; $finish )
{
    return $this-&gt;binarySearch( $date, $mid + 1, $max );
}

return $node;


Minor optimization

The find method recalculates the size of $this-&gt;nodes,
even though it cannot change after construction.
It would be better to calculate the size once,
at construction time.