一、什么是二分查找？

二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。

二、时间复杂度分析？

  1. 时间复杂度
    假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。
  2. 认识O(logn)
    1. 这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？
    2. 因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。
    3. 由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。

三、如何实现二分查找？

循环实现

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 循环实现二分查找
public function bsearchLoop(array $array, int $n, $value)
{
    $low = 0;
    $high = $n - 1;
    while ($low <= $low) {
        $mid = $low + (($high - $low) >> 1);
        if ($array[$mid] > $value) {
            $high = $mid - 1;
        } elseif ($array[$mid] < $value) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }
    return -1;
}

注意事项：

  1. 循环退出条件是：low<=high，而不是low<high。
  2. mid的取值，使用mid=low + (high - low) / 2，而不用mid=(low + high)/2，因为如果low和high比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即low + ((high - low) >> 1)，因为相比除法运算来说，计算机处理位运算要快得多。
  3. low和end的更新：low = mid - 1，high = mid + 1，若直接写成low = mid，high=mid，就可能会发生死循环。

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 递归实现二分查找
public function bsearchRecursion(array $array, int $n, $value)
{
    return $this->bSear($array, $value, 0, $n - 1);
}

private function bSear(array $array, $value, int $low, int $high)
{
    if ($low > $high) {
        return -1;
    }
    $mid = $low + (($high - $low) >> 2);
    if ($array[$mid] == $value) {
        return $mid;
    } elseif ($array[$mid] > $value) {
        $high = $mid - 1;
    } else {
        $low = $mid + 1;
    }
    return $this->bSear($array, $value, $low, $high);
}

四、使用条件（应用场景的局限性）

  1. 二分查找依赖的是顺序表结构，即数组。
  2. 二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
  3. 数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但有一个例外，就是数据之间的比较操作非常费时，比如数组中存储的都是长度超过300的字符串，那这是还是尽量减少比较操作使用二分查找吧。
  4. 数据量太大也不是适合用二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间。

五、递归变体

1.查找第一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 变体1. 查找第一个值等于给定值的元素
public function bsearch1($array, int $n, $value)
{
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($array[$mid] > $value) {
            $high = $mid - 1;
        } elseif ($array[$mid] < $value) {
            $low = $mid + 1;
        } else {
            if ($mid == 0 || $array[$mid - 1] != $value) {
                return $mid;
            } else {
                $high = $mid - 1;
            }
        }
    }
    return -1;
}

2.查找最后一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 变体2. 查找最后一个值等于给定值的元素
public function bsearch2(array $array, int $n, $value)
{
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($array[$mid] > $value) {
            $high = $mid - 1;
        } elseif ($array[$mid] < $value) {
            $low = $mid + 1;
        } else {
            if ($mid == $n - 1 || $array[$mid + 1] != $value) {
                return $mid;
            } else {
                $low = $mid + 1;
            }
        }
    }
    return -1;
}

3.查找第一个大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 变体3. 查找第一个大于等于给定值的元素
public function bsearch3(array $array, int $n, $value)
{
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($array[$mid] >= $value) {
            if ($mid == 0 || $array[$mid - 1] < $value) {
                return $mid;
            } else {
                $high = $mid - 1;
            }
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

4.查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 变体4. 查找最后一个小于等于给定值的元素
public function bsearch4(array $array, int $n, $value)
{
    $low = 0;
    $high = $n - 1;
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($array[$mid] > $value) {
            $high = $mid - 1;
        } else {
            if ($mid == $n - 1 || $array[$mid + 1] > $value) {
                return $mid;
            } else {
                $low = $mid + 1;
            }
        }
    }
    return -1;
}

六、思考

  1. 如何在1000万个整数中快速查找某个整数？
    1. 1000万个整数占用存储空间为40MB，占用空间不大，所以可以全部加载到内存中进行处理；
    2. 用一个1000万个元素的数组存储，然后使用快排进行升序排序，时间复杂度为O(nlogn)
    3. 在有序数组中使用二分查找算法进行查找，时间复杂度为O(logn)
  2. 如何编程实现“求一个数的平方根”？要求精确到小数点后6位？