二分查找是从一组有序数组中查找某特定元素，搜索过程是从中间开始查找，如果中间值非查找元素，那么从小于或大于中间元素的一半数组中查找，一样是从中间开始匹配

检查元素是否存在，流程如图

图片发自简书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;