PHP: Bisect Left & Bisect Right using Binary Search (similar to Python's bisect_left & bisect_right). Binary search only works on sorted arrays. Arrays must be first sorted with quick sort. Bisect right finds the index of a value where all the elements from left to right up to the index is less or equal to the value: Array: [1, 1, 2, 2, 3, 4] Va…

bisecting_binary_search.php

<?php

// sorted array must be a 0 indexed
// left most index, right most index all inclusive
// finds all of the elements coming from the left to the right that is less or equal to the key
function bisect_right($sorted_array, $key, $left = null, $right = null){

    if(is_null($left)){
        reset($sorted_array);
        $left = key($sorted_array);
    }

    if(is_null($right)){
        end($sorted_array);
        $right = key($sorted_array);
        reset($sorted_array);
    }

    if ($key < $sorted_array[$left]){
        return 0;
    }elseif ($key >= $sorted_array[$right]){
        return count($sorted_array);
    }

    // this section only works for keys that are within the range and exclusive of the last element

    // converging upon compact range L,R where R-L = 1, where L can potentially equal the key
    while ($right - $left > 1) {

        // the middle when converted to an integer is biased to the left
        $middle = intval(($left + $right) / 2);

        // the left can potentially equal the key's position
        if($key >= $sorted_array[$middle]){
            $left = $middle;
        }else{
            $right = $middle;
        }

    }

    // right will always be to the right of the rightmost key (which is the left), left + 1 = right, as left and right has converged
    // therefore right is the number of elements less or equal to the key
    return $right;

}

// sorted array must be a 0 indexed
// left most index, right most index all inclusive
// finds all of the elements coming from the left to the right that is less than the key
function bisect_left($sorted_array, $key, $left = null, $right = null){

    if(is_null($left)){
        reset($sorted_array);
        $left = key($sorted_array);
    }
    
    if(is_null($right)){
        end($sorted_array);
        $right = key($sorted_array);
        reset($sorted_array);
    }

    if ($key < $sorted_array[$left]) {
        return 0;
    }elseif ($key >= $sorted_array[$right]) {
        return count($sorted_array);
    }

    // this section only works for keys that are within the range and exclusive of the last element

    // converging upon compact range L,R where R-L = 1, where R can potentially equal the key
    while($right - $left > 1){

        // the middle when converted to an integer is biased to the left
        $middle = intval(($left + $right) / 2);

        echo "$middle <= MIDDLE\n";

        // the right can potentially equal the key's position
        if ($key <= $sorted_array[$middle]) {
            $right = $middle;
        }else{
            $left = $middle;
        }

    }

    // left will always be to the left of the leftmost key (which is the right), left + 1 = right, as left and right has converged
    // therefore right is the number of elements less than the key
    return $right;

}

$a = [2=>-4, -1, 0, 0, 0, 0, 2, 5];
$b = 0;
var_dump(bisect_left($a, $b));

Obligatory practical example (e.g. why you might need this) I often use as an interview question: given a sorted list of opening and closing times (say, as tuples, given I'm a Python programmer):

times = [
	('09:00', True),
	('12:00', False),
	('13:00', True),
	('17:00', False)
]

Determine the state of the store at 16:15:

state = times[bisect_left(times, ('16:15', None))][1]

if state:
	print("The store is open.")
else:
	print("Closed.")

Great stuff! Though there is a small bug in line 81 which is fixed in my library https://github.com/ddlzz/bisect so for everyone who reads this: feel free to use it in your projects!