二分查找是从一组有序数组中查找某特定元素，搜索过程是从中间开始查找，如果中间值非查找元素，那么从小于或大于中间元素的一半数组中查找，一样是从中间开始匹配
检查元素是否存在，流程如图
图片发自简书App
/**
* 查找元素是否在数组中，返回其位置
* @param $key
* @param array $data
* @param $dataSize
* @return float|int
*/
public function search($key, array $data, $dataSize)
{
$low = 0;
$high = $dataSize - 1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if ($data[$mid] < $key){
$low = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
查找第一次出现位置
图片发自简书App
图片发自简书App
/**
* 查找第一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findFirst(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($data[$mid] === $key){
$out = $mid;
$high = $mid - 1;
} else if($data[$mid] > $key){
$high = $mid - 1;
} else {
$low = $mid + 1;
}
}
return $out;
}
查找最后一次出现位置
image.png
/**
* 查找最后一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findLast(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if($key === $data[$mid]){
$low = $mid + 1;
$out = $mid;
} else {
$low = $mid + 1;
}
}
return $out;
}
时间复杂度为: O（log n）
代码实现
<?php
namespace Patterns\Algorithm;
class BinarySearch
{
/**
* 查找元素是否在数组中，返回其位置
* @param $key
* @param array $data
* @param $dataSize
* @return float|int
*/
public function search($key, array $data, $dataSize)
{
$low = 0;
$high = $dataSize - 1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if ($data[$mid] < $key){
$low = $mid + 1;
} else {
return $mid;
}
}
return -1;
}
/**
* 查找第一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findFirst(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($data[$mid] === $key){
$out = $mid;
$high = $mid - 1;
} else if($data[$mid] > $key){
$high = $mid - 1;
} else {
$low = $mid + 1;
}
}
return $out;
}
/**
* 查找最后一次出现
* @param int $key
* @param array $data
* @param int $dataSize
* @return int
*/
public function findLast(int $key, array $data, int $dataSize):int
{
$low = 0;
$high = $dataSize - 1;
$out = -1;
if($dataSize < 0){
return -1;
}
while($low <= $high){
//防止大数溢出，如果不考虑遇到大数溢出时可用：floor((low + high) / 2)
$mid = $low + floor(($high - $low) >> 1);
if($key < $data[$mid]){
$high = $mid - 1;
} else if($key === $data[$mid]){
$low = $mid + 1;
$out = $mid;
} else {
$low = $mid + 1;
}
}
return $out;
}
}
include_once "./Sort.php";
$array = [3, 5, 7, 7, 7, 7, 7, 7, 10, 10, 10, 15, 17, 18, 18, 35, 78, 78];
$sort = new Sort();
$array = $sort->quick($array);
$sortSearch = new BinarySearch();
$needle = 1;
echo 'exists: ' . $sortSearch->search($needle, $array, count($array)), PHP_EOL;
echo 'First: ' . $sortSearch->findFirst($needle, $array, count($array)), PHP_EOL;
echo 'Last: ' . $sortSearch->findLast($needle, $array, count($array)), PHP_EOL;
