[算法]二分查找

适用场景

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

核心思路

• 维护一个搜索区间，通常是 [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: &[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
}

代表题

• 33. 搜索旋转排序数组
  题意：给定一个经过旋转的升序数组和目标值 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 mid_value = nums[mid as usize];

        if mid_value == target {
            return mid;
        }

        if nums[left as usize] <= mid_value {
            if nums[left as usize] <= target && target < mid_value {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else if mid_value < target && target <= nums[right as usize] {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    -1
}

• 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]
}

• 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
}

• 4. 寻找两个正序数组的中位数
  题意：给定两个有序数组，求它们合并后的中位数，要求时间复杂度尽量低。

fn kth(nums1: &[i32], nums2: &[i32], mut k: usize) -> i32 {
    let mut i = 0usize;
    let mut j = 0usize;

    loop {
        if i == nums1.len() {
            return nums2[j + k - 1];
        }
        if j == nums2.len() {
            return nums1[i + k - 1];
        }
        if k == 1 {
            return nums1[i].min(nums2[j]);
        }

        let half = k / 2;
        let ni = (i + half).min(nums1.len()) - 1;
        let nj = (j + half).min(nums2.len()) - 1;

        if nums1[ni] <= nums2[nj] {
            k -= ni - i + 1;
            i = ni + 1;
        } else {
            k -= nj - j + 1;
            j = nj + 1;
        }
    }
}

pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let total = nums1.len() + nums2.len();

    if total % 2 == 1 {
        kth(&nums1, &nums2, total / 2 + 1) as f64
    } else {
        let left = kth(&nums1, &nums2, total / 2) as f64;
        let right = kth(&nums1, &nums2, total / 2 + 1) as f64;
        (left + right) / 2.0
    }
}

• 74. 搜索二维矩阵
  题意：给定一个按行升序、且每行首元素大于上一行末元素的矩阵，判断目标值是否存在。

pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut left = 0i32;
    let mut right = (m * n) as i32 - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        let row = mid as usize / n;
        let col = mid as usize % n;
        let value = matrix[row][col];

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

    false
}

• 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]
}

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

pub fn binary_search_exact(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
}

• 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
}