PHP有序表查找之二分查找（折半查找）算法示例

下面我将对“PHP有序表查找之二分查找（折半查找）算法示例”的完整攻略进行详细讲解。

一、什么是二分查找

二分查找又称为折半查找，是一种在有序数组中查找某一特定元素的搜索算法。基本思想是：将有序数组分成两部分，如果要查找的元素比数组中间的元素小，则在左半部分继续查找；如果要查找的元素比数组中间的元素大，则在右半部分继续查找，直到找到或者查找结束。

二分查找算法的时间复杂度为 O(logn)，比简单查找算法 O(n) 更快。

二、二分查找的实现

下面，我们以 PHP 语言为例，演示如何实现二分查找算法。

1. 二分查找示例一

function binarySearch($arr, $val) {
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);
        if ($arr[$mid] === $val) {
            return $mid;
        } elseif ($arr[$mid] < $val) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1;
}

$arr = [3, 7, 8, 13, 23, 27, 34, 38, 42, 45, 53, 57, 69, 78];
$val = 42;

$key = binarySearch($arr, $val);

if ($key == -1) {
    echo '查找失败！';
} else {
    echo '数值 ' . $val . ' 在数组中的索引位置是 ' . $key . '。';
}

上面的代码实现了一个二分查找函数 binarySearch()，使用该函数可查找数组 $arr 中是否存在数值 $val。如果存在，返回该数值在数组中的索引位置；如果不存在，返回 -1。

在上面的示例中，我们先定义了一个有序数组 $arr，然后将 $val 设为 42。最后，调用 binarySearch() 函数进行查找，并根据返回结果输出查找结果。

2. 二分查找示例二

下面是另一个示例，演示如何使用二分查找算法在一个多维数组中查找某个字符串。

function binarySearchMultiArray($array, $searchStr) {
    $left = 0;
    $right = count($array) - 1;
    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);
        $item = $array[$mid];
        $compare = strcmp($searchStr, $item['str']);
        if ($compare === 0) {
            return $mid;
        } elseif ($compare < 0) {
            $right = $mid - 1;
        } else {
            $left = $mid + 1;
        }
    }
    return -1;
}

$multiArray = [
    ['id' => 1, 'str' => 'apple'],
    ['id' => 2, 'str' => 'banana'],
    ['id' => 3, 'str' => 'cherry'],
    ['id' => 4, 'str' => 'durian'],
    ['id' => 5, 'str' => 'elderberry'],
    ['id' => 6, 'str' => 'fig'],
    ['id' => 7, 'str' => 'grape'],
    ['id' => 8, 'str' => 'honeydew'],
];

$searchStr = 'fig';

$key = binarySearchMultiArray($multiArray, $searchStr);

if ($key == -1) {
    echo '查找失败！';
} else {
    echo '字符串 ' . $searchStr . ' 在多维数组中的索引位置是 ' . $key . '。';
}

在上面的示例中，我们定义了一个多维数组 $multiArray，然后使用 binarySearchMultiArray() 函数查找数组中是否存在字符串 $searchStr。如果存在，则返回该字符串在数组中的索引位置；否则返回 -1。最后，根据函数返回结果输出查找结果。

三、小结

二分查找算法是一种重要的搜索算法，它可以在有序数组中快速查找某个元素。在实际开发中，我们可以根据不同的需求，灵活应用二分查找算法。