Implement BinarySearch with php


class BinarySearch
{
    private $start              = null;
    private $end                = null;
    private $calculatedLength   = null;
    private $elements           = array();
    private $searchingEliment   = null;



    /**
     * @param $searchEliment
     * @param array $eliments
     * @return int
     */
    public function search($searchEliment, array $eliments = array())
    {
        $this->searchingEliment = (int) $searchEliment;
        $this->elements         = $eliments;
        $totalElement           = count($this->elements);
        $currentElement         = current($this->elements);
        $this->start            = 0;
        $this->end              = $totalElement - 1;

        if (($totalElement == 0) || ($totalElement == 1
                && $currentElement != $this->searchingEliment))
            return -1;

        if ($totalElement == 1 && $currentElement == $this->searchingEliment)
            return $this->start;

        while (true) {

            $this->calculatedLength = $this->start + $this->end;

            if ($this->calculatedLength == 1) {
                if ($this->elements[$this->start] == $this->searchingEliment) {
                    return $this->start;
                } else if ($this->elements[$this->end] == $this->searchingEliment) {
                    return $this->end;
                } else {
                    return -1;
                }
            }

            $mid = ceil($this->calculatedLength / 2);

            if ($this->elements[$mid] == $this->searchingEliment)
                return $mid;

            if ($this->end == $mid)
                return -1;

            if ($this->elements[$mid] < $this->searchingEliment)
                $this->start = $mid;

            if ($this->elements[$mid] > $this->searchingEliment)
                $this->end = $mid;
        }

    }
}





class BinarySearchTest extends PHPUnit_Framework_TestCase
{

    public function testBinarySearchReturnIndex()
    {
        $binarySearch = new RequiresiveBinarySearch();
        $this->assertEquals($binarySearch->search(2, array(1, 2)), 1);


        $this->assertEquals($binarySearch->search(3, array()), -1);
        $this->assertEquals($binarySearch->search(3, array()), -1);

        $this->assertEquals(-1, $binarySearch->search(3, [1]));
        $this->assertEquals(0,  $binarySearch->search(1, [1]));

        $this->assertEquals(0,  $binarySearch->search(1, [1, 3, 5]));
        $this->assertEquals(1,  $binarySearch->search(3, [1, 3, 5]));
        $this->assertEquals(2,  $binarySearch->search(5, [1, 3, 5]));
        $this->assertEquals(-1, $binarySearch->search(0, [1, 3, 5]));
        $this->assertEquals(-1, $binarySearch->search(2, [1, 3, 5]));
        $this->assertEquals(-1, $binarySearch->search(4, [1, 3, 5]));
        $this->assertEquals(-1, $binarySearch->search(6, [1, 3, 5]));

        $this->assertEquals(0,  $binarySearch->search(1, [1, 3, 5, 7]));
        $this->assertEquals(1,  $binarySearch->search(3, [1, 3, 5, 7]));
        $this->assertEquals(2,  $binarySearch->search(5, [1, 3, 5, 7]));
        $this->assertEquals(3,  $binarySearch->search(7, [1, 3, 5, 7]));
        $this->assertEquals(-1, $binarySearch->search(0, [1, 3, 5, 7]));
        $this->assertEquals(-1, $binarySearch->search(2, [1, 3, 5, 7]));
        $this->assertEquals(-1, $binarySearch->search(4, [1, 3, 5, 7]));
        $this->assertEquals(-1, $binarySearch->search(6, [1, 3, 5, 7]));
        $this->assertEquals(4, $binarySearch->search(67, [1, 3, 5, 7, 67]));
        $this->assertEquals(-1, $binarySearch->search(8, [1, 3, 5, 7]));

    }


}

Leave a Reply

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