<?php
/**
 * 二分查找
 * 注意：必须是顺序的序列
 *
 * User: Vega.Lee
 * Date: 2020/6/13
 * Time: 19:34
 */


/**
 * @param $arr
 *  这个数组的排序是从小到大的
 * @param $left
 * @param $right
 * @param $searchValue
 * @return int
 *  返回只是单个值，若有相同的则不能一起查找出来
 */
function aichotomySearch ($arr, $left, $right, $searchValue)
{

    //判断当左指针不在大于右指针或者超过数组最大值最小值时，进行返回处理
    if (($left > $right) || ($arr[0] > $searchValue || $arr[count($arr) - 1] < $searchValue))
    {
        return -1;
    }

    $middle_index = intval(($left + $right) / 2);

    if ($arr[$middle_index] <  $searchValue)
    {
        //如果比中间值大则向右移
        return aichotomySearch($arr, $middle_index + 1, $right, $searchValue);
    }
    elseif ($arr[$middle_index] >  $searchValue)
    {
        //如果比中间值大则向左移
        return aichotomySearch($arr, $left, $middle_index - 1, $searchValue);
    }
    else
    {
        return $middle_index;
    }


}


/**
 * 查找多个值
 * @param $arr
 * @param $left
 * @param $right
 * @param $searchValue
 * @return array|int
 */
function aichotomySearchMultiple ($arr, $left, $right, $searchValue)
{
    //定义一个存储容器
    static $searchArr = [];

    //判断当左指针不在大于右指针或者超过数组最大值最小值时，进行返回处理
    if (($left > $right) || ($arr[0] > $searchValue || $arr[count($arr) - 1] < $searchValue))
    {
        return -1;
    }

    $middle_index = intval(($left + $right) / 2);

    if ($arr[$middle_index] <  $searchValue)
    {
        //如果比中间值大则向右移
        return aichotomySearchMultiple($arr, $middle_index + 1, $right, $searchValue);
    }
    elseif ($arr[$middle_index] >  $searchValue)
    {
        //如果比中间值大则向左移
        return aichotomySearchMultiple($arr, $left, $middle_index - 1, $searchValue);
    }
    else
    {

        //如果找到后则向左和向右分别去找相同的值放到容器中
        $searchArr[] = $middle_index;
        $temp_middle_left_index = $middle_index - 1;
        $temp_middle_right_index = $middle_index + 1;

        while ($temp_middle_left_index >= $left)
        {
            if ($arr[$temp_middle_left_index] == $arr[$middle_index])
            {
                $searchArr[] = $temp_middle_left_index;

                $temp_middle_left_index--;

            }
            else
            {
                break;
            }

        }

        while ($temp_middle_right_index <= $right)
        {
            if ($arr[$temp_middle_right_index] == $arr[$middle_index])
            {
                $searchArr[] = $temp_middle_right_index;

                $temp_middle_right_index++;
            }
            else
            {
                break;
            }
        }


        return $searchArr;

    }


}

$arr = [1,3,3,3,5,5,5,10];

$search = aichotomySearchMultiple($arr, 0, count($arr) - 1, 5);

var_dump($search);