<?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);