二分查找算法速记

jiezi

6 年前

二分查找 （英语：binary search），也称 折半搜索 （英语：half-interval search） 对数搜索（英语：logarithmic search，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

适合的场景：

Sorted（单调递增或者递减）
Bounded（存在上下界，因为要一分为二的进行查找）
Accessible by index（能够通过索引访问）

时间复杂度：

O(logN)

空间复杂度:

O(N) 使用常数空间，无论任何大小的输入数据，算法使用的空间都是一样的

适用的数据结构：

数组，因为在内存中时连续的适合使用二分查找。但是链表不适合，因为链表坐标不是固定的，访问 a[2]需要先从 a[0]的后继节点找到 a[1]再通过 a[1]的后继节点才能访问到 a[2]。

步骤：

初始状态 left、right 分别指向数组的头和尾。
通过(left + right) /2 得到中间位置 mid，访问数组中 mid 位置的元素。
判断其与查找目标的大小关系，相等则程序返回，
比目标小则挪动 left 指针到 mid + 1；比目标大则挪动 right 指针到 mid – 1
重复上面步骤 2 ～ 3 直到找到目标元素或者程序退出。

代码实现:

<?php

$list = [1, 2, 5, 6, 8, 9, 12, 15, 23, 32, 56, 67, 73, 85];

function bioSearch($list, $target)
{
    $left = 0;
    $right = count($list) - 1;
    while ($left <= $right) {$mid = ($left + $right) / 2;
        if ($list[$mid] == $target) {return true;} else if ($list[$mid] < $target) {
            $left = $mid + 1;
            continue;
        } else {
            $right = $mid - 1;
            continue;
        }
    }

    return false;
}