[算法]二分查找

适用场景

• 题目给出的数组或答案空间具有 单调性
• 需要在 有序数组 中快速定位目标值
• 需要求 第一个满足条件 或 最后一个满足条件 的位置
• 有些题不是直接查数组，而是对 答案 进行二分

核心思路

• 维护一个搜索区间，通常是 [left, right]
• 每次取中点 mid = left + (right - left) / 2
• 根据 mid 是否满足条件，决定丢弃左半边还是右半边
• 不断缩小区间，直到找到答案或区间为空

Rust 模板

fn binary_search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0i32;
    let mut right = nums.len() as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        let value = nums[mid as usize];

        if value == target {
            return mid;
        } else if value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    -1
}

查找左边界

fn lower_bound(nums: Vec<i32>, target: i32) -> usize {
    let mut left = 0usize;
    let mut right = nums.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if nums[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    left
}

代表题

• 704. 二分查找
  题意：给定一个升序整数数组和一个目标值 target，若目标值存在则返回下标，否则返回 -1。

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0i32;
    let mut right = nums.len() as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        let value = nums[mid as usize];

        if value == target {
            return mid;
        } else if value < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    -1
}

• 35. 搜索插入位置
  题意：给定一个升序数组和目标值 target，找到目标值所在位置；如果不存在，返回它按顺序应插入的位置。

pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0usize;
    let mut right = nums.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if nums[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    left as i32
}

• 34. 在排序数组中查找元素的第一个和最后一个位置
  题意：给定一个按非递减顺序排列的数组，找出目标值 target 的起始位置和结束位置；如果不存在则返回 [-1, -1]。

fn lower_bound(nums: &[i32], target: i32) -> usize {
    let mut left = 0usize;
    let mut right = nums.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    left
}

pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let left = lower_bound(&nums, target);

    if left == nums.len() || nums[left] != target {
        return vec![-1, -1];
    }

    let right = lower_bound(&nums, target + 1) - 1;
    vec![left as i32, right as i32]
}

• 153. 寻找旋转排序数组中的最小值
  题意：给定一个原本升序、经过若干次旋转的数组，数组中元素互不相同，找出其中的最小值。

pub fn find_min(nums: Vec<i32>) -> i32 {
    let mut left = 0usize;
    let mut right = nums.len() - 1;

    while left < right {
        let mid = left + (right - left) / 2;

        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    nums[left]
}

• 875. 爱吃香蕉的珂珂
  题意：给定若干堆香蕉和总时长 h，求珂珂在 h 小时内吃完所有香蕉的最小速度。

pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
    let mut left = 1;
    let mut right = *piles.iter().max().unwrap();

    while left < right {
        let mid = left + (right - left) / 2;
        let mut hours = 0i64;

        for &pile in &piles {
            hours += ((pile as i64) + (mid as i64) - 1) / mid as i64;
        }

        if hours <= h as i64 {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    left
}