Binary Search

二分查找（binary search） 是基于分治策略的搜索算法，它利用数据有序性，每次搜索减少一半搜索范围。

• 时间复杂度 $O(\log n)$
• 空间复杂度 $O(1)$

区间表示方法

[low, high] 左闭右闭

由于 low、high 左右边界都是可达的，缩小的操作区间也是对称的，因此更推荐使用本方法，更不容易出错。但是 high 可能为负数（-1），因此在 rust 中需要使用 checked_sub 方法来避免溢出。

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.lenMIN?;
    while left <= right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less => right = mid.checked_subMIN?,
            Ordering::Equal => return Ok(mid),
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    Err(left)
}

[low, high) 左闭右开

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.len();
    while left < right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less => right = mid,
            Ordering::Equal => return Ok(mid),
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    Err(left)
}

变体

由于变体需要循环退出后才判断是否找到，因此使用左开右闭更简单，因为退出循环一定意味着两者相等。

找到第一个出现的

[low, high] 左闭右闭

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.lenMIN?;
    while left <= right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less  => right = mid.checked_subMIN?,
            Ordering::Equal => {
                right = match mid.checked_sub(1) {
                    Some(x) => x,
                    None => break,
                }
            },
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    if left != arr.len() && target.eq(&arr[left]) {
        Ok(left)
    } else {
        Err(left)
    }
}

[low, high) 左闭右开

最后返回 left 或 right 都无所谓，因为退出循环一定意味着两者相等。

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.len();
    while left < right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less | Ordering::Equal => right = mid,
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    if left != arr.len() && target.eq(&arr[left]) {
        Ok(left)
    } else {
        Err(left)
    }
}

找到最后一个出现的

[low, high] 左闭右闭

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.lenMIN?;
    while left <= right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less => right = mid.checked_subMIN?,
            Ordering::Equal => {
                left = match mid.checked_add(1) {
                    Some(x) => x,
                    None => break,
                }
            }
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    if left != 0 && target.eq(&arr[left - 1]) {
        Ok(left - 1)
    } else {
        Err(left)
    }
}

[low, high) 左闭右开

最后返回 left 或 right 都无所谓，因为退出循环一定意味着两者相等。

use std::cmp::Ordering;

pub fn search<T: Ord>(arr: &[T], target: &T) -> Result<usize, usize> {
    let mut left = 0;
    let mut right = arr.len();
    while left < right {
        let mid = left + (right - left) / 2;
        match target.cmp(&arr[mid]) {
            Ordering::Less => right = mid,
            Ordering::Equal => {
                left = match mid.checked_add(1) {
                    Some(x) => x,
                    None => break,
                }
            }
            Ordering::Greater => left = mid.checked_addMAX?,
        };
    }
    if left != 0 && target.eq(&arr[left - 1]) {
        Ok(left - 1)
    } else {
        Err(left)
    }
}

局限

• 仅适用于有序数据
  • 若输入数据无序，排序通常时间复杂度为 $O(n\log n)$ ，比线性查找、二分查找都高
• 二分查找只适用于数组
  • 需要非连续地访问元素，不适用于链表
• 小数量下线性查找性能更好