在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array

问题描述

这个问题适合用二分查找法.

基本的二分查找法

分两步来解这个问题:

  1. 使用二分查找法确定 target 存在于数组中, 如果不存在就直接返回; 如果存在, 就得到了它的索引值 middle
  2. 然后使用线性查找法, 分别从 middle 开始向数组的左右两端查找与 target 元素相等的

最后的实现代码如下所示:

#![allow(unused)]
fn main() {
use std::cmp::Ordering;

// Binary search
pub fn search_range1(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut result = vec![-1, -1];
    let len = nums.len();

    // 处理极端情况
    if len == 0 || nums[0] > target || nums[len - 1] < target {
        return result;
    }

    let mut low = 0;
    let mut high = len - 1;
    let mut middle = 0;
    while low <= high {
        middle = low + (high - low) / 2;
        match nums[middle].cmp(&target) {
            Ordering::Less => low = middle + 1,
            Ordering::Equal => break,
            Ordering::Greater => {
                if middle > 1 {
                    high = middle - 1;
                } else {
                    // 没有找到
                    return result;
                }
            }
        }
    }

    // 退化成线性查找
    let mut i = middle as i32;
    while i >= 0 && nums[i as usize] == target {
        result[0] = i;
        i -= 1;
    }
    let mut i = middle;
    while i < len && nums[i] == target {
        result[1] = i as i32;
        i += 1;
    }
    result
}
}

这个是对上述方法的简化, 使用标准库中自带的二分查找算法:

#![allow(unused)]
fn main() {
// 使用 slice::binary_search()
pub fn search_range2(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut result = vec![-1, -1];
    let len = nums.len();

    // 处理极端情况
    if len == 0 || nums[0] > target || nums[len - 1] < target {
        return result;
    }

    let middle = match nums.binary_search(&target) {
        Ok(index) => index,
        Err(_) => return result,
    };

    // 退化成线性查找
    let mut i = middle as i32;
    while i >= 0 && nums[i as usize] == target {
        result[0] = i;
        i -= 1;
    }
    let mut i = middle;
    while i < len && nums[i] == target {
        result[1] = i as i32;
        i += 1;
    }
    result
}
}

两次二分查找

上面的算法, 对于查找与 target 相等的元素时, 使用了两次线性查找, 用于确定左右边界. 这一步时间复杂度是 O(k), 其中的 k 是与 target 相等的元素的个数.

我们可以使用两次二分查找法, 取代线性查找法, 直接确定左右边界.

#![allow(unused)]
fn main() {
// 两次二查找法
// 如果 `target` 在数组中的个数比较多, 这种算法效率很高, `O(log n)`
pub fn search_range3(nums: Vec<i32>, target: i32) -> Vec<i32> {
    fn search_left(nums: &[i32], target: i32) -> i32 {
        let len = nums.len();
        // 极端情况
        if len == 0 || nums[0] > target || nums[len - 1] < target {
            return -1;
        }

        // 极端情况
        if nums[0] == target {
            return 0;
        }

        let mut left = 1;
        let mut right = len - 1;
        let mut low: i32 = -1;
        while left <= right {
            let middle = left + (right - left) / 2;
            match nums[middle].cmp(&target) {
                Ordering::Less => left = middle + 1,
                Ordering::Equal => {
                    low = middle as i32;
                    // 即使当前元素等于 target, 也要调整右侧的索引向左移动
                    right = middle - 1;
                }
                // 这里不需使用 saturating_sub() 防止右侧索引 underflow,
                // 因为 middle >= left >= 1
                Ordering::Greater => right = middle - 1,
            }
        }
        low
    }

    fn search_right(nums: &[i32], target: i32) -> i32 {
        let len = nums.len();
        // 极端情况
        if len == 0 || nums[0] > target || nums[len - 1] < target {
            return -1;
        }

        // 极端情况
        if nums[len - 1] == target {
            return len as i32 - 1;
        }

        let mut left = 0;
        let mut right = len - 2;
        let mut high: i32 = -1;
        while left <= right {
            let middle = left + (right - left) / 2;
            match nums[middle].cmp(&target) {
                Ordering::Less => left = middle + 1,
                Ordering::Equal => {
                    high = middle as i32;
                    // 即使当前元素等于 target, 也要调整左侧索引向右移动
                    left = middle + 1;
                }
                // 这里使用 saturating_sub() 防止右侧索引 underflow
                Ordering::Greater => right = middle.saturating_sub(1),
            }
        }
        high
    }

    vec![search_left(&nums, target), search_right(&nums, target)]
}
}