用Rust🦀写算法-数组篇-二分查找

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入:nums = [-1,0,3,5,9,12],target = 9
输出: 4
解释: 9 出现在nums 中并且下标为 4

示例 2:

1
2
3
输入:nums = [-1,0,3,5,9,12],target = 2
输出: -1
解释: 2 不存在nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

💡 思路：
有序数组 数组中无重复元素 ⇒ 二分查找
当数组中有重复元素，使用二分查找法返回的元素下标可能不是唯一的

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

写法一（左闭右闭）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0i32;
        let mut right = nums.len() as i32 -1; //nums.len()返回usize -1会导致溢出 改为i32

        while left <= right {
            let middle = left + (right - left) / 2; 
            match nums[middle as usize].cmp(&target) {
                std::cmp::Ordering::Less => left = middle + 1,
                std::cmp::Ordering::Greater => right = middle -1,
                std::cmp::Ordering::Equal => return middle,
            }
        }
        -1
		}
}

在 Rust 中，**0usize - 1** 会导致 panic（程序崩溃），因为 usize 是无符号整数（不能为负数），而减法下溢（underflow）在 debug 模式下会触发 panic。

💡 在Release 模式下（-release 编译）由于溢出检查被禁用
代码let right = 0usize - 1;的结果会按照无符号整数的回绕（wrapping）规则计算：
0usize - 1 = usize::MAX（例如 64 位系统上是 18446744073709551615）
这会导致后续的数组访问越界（nums[middle] 会 panic），因为索引远大于数组长度。

写法二（左闭右开）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len(); //因为是开区间不用-1

        while left < right {
            let middle = left + (right - left) / 2; 
            match nums[middle].cmp(&target) {
                std::cmp::Ordering::Less => left = middle + 1,
                std::cmp::Ordering::Greater => right = middle, //开区间
                std::cmp::Ordering::Equal => return middle as i32,
            }
        }
        -1
		}
}

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • 104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • 104 <= target <= 104

💡 思路：
nums 为 无重复元素 的 升序 排列数组，有序数组 + 无重复数据 尝试使用二分法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use std::cmp::Ordering;
impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        let mut middle;

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

            match nums[middle].cmp(&target) {
                Ordering::Less => left = middle + 1,
                Ordering::Greater => right = middle,
                Ordering::Equal => return middle as i32,
            }
        }
        left as i32
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        nums.partition_point(|&x| x < target) as _
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • 109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • 109 <= target <= 109

💡 思路： 非递减 → 有序 但是 数组中有重复数据 → 二分查找变式

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
use std::cmp::Ordering;
impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let start = Self::binary_search_fast(&nums,target);
        let end = Self::binary_search_last(&nums,target);
        if start <= end {
            return [start,end].to_vec();
        }else{
            return [-1,-1].to_vec();
        }
    }

		// 二分查找变式 当nums[middle] == &target时，依旧向左查找
    fn binary_search_fast(nums: &[i32], target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        let mut middle;

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

            match nums[middle].cmp(&target) {
                Ordering::Less => left = middle + 1,
                Ordering::Greater | Ordering::Equal => right = middle,//相等时，依旧缩小左边区间 接下来left会持续+1到第一个等于target的下标
            }
        }
        left as i32
    }

		// 二分查找变式 当nums[middle] == &target时，依旧向右查找
    fn binary_search_last(nums: &[i32], target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        let mut middle;

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

            match nums[middle].cmp(&target) {
                Ordering::Less | Ordering::Equal => left = middle + 1,//相等时，依旧缩小右边区间 接下来left会持续+1到第一个大于target的下标
                Ordering::Greater => right = middle,
            }
        }
        left as i32 - 1 //大于target的第一个下表 所以 -1
    }
}

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
use std::cmp::Ordering;

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        // 数据为空 直接返回
        if nums.is_empty() {
            return vec![-1, -1];
        }

        let first_pos = Self::find_boundary(&nums, target, true);
        
        // 没有查询到target 直接返回
        if first_pos == -1 {
            return vec![-1, -1];
        }
        
        let last_pos = Self::find_boundary(&nums, target, false);
        vec![first_pos, last_pos]
    }

    /// 统一函数
    /// 当find_first = true时，查找出现target的第一个位置
    /// 当find_first = false时，查找出现target的最后一个位置
    fn find_boundary(nums: &[i32], target: i32, find_first: bool) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        let mut result = -1;
        
        while left < right {
            let mid = left + (right - left) / 2;
            
            match nums[mid].cmp(&target) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid,
                Ordering::Equal => {
                    result = mid as i32;
                    if find_first {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
            }
        }
        
        result
    }
}

利用标准库：

1
2
3
4
5
6
7
8
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let left = nums.partition_point(|&x| x < target);
    if left == nums.len() || nums[left] != target {
        return vec![-1, -1];
    }
    let right = nums.partition_point(|&x| x <= target) - 1;
    vec![left as i32, right as i32]
}

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

1
2
输入：x = 4
输出：2

示例 2：

1
2
3
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 2^31 - 1

💡 思路：
对于非负整数 m 来说，由于 m 越小越满足 m²≤x，m 越大越不满足 m²≤x，有单调性，可以二分答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
use std::cmp::Ordering;
impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut left = 0;
        let mut right = x.min(46340) + 1;// 开区间（left，right）

        while left + 1 < right{ //开区间不为空
            let middle = left + (right - left) / 2;

            match middle.cmp(&(x / middle)) {
                Ordering::Less | Ordering::Equal => left = middle,
                Ordering::Greater => right = middle,
            }
        }
        // 循环结束 left + 1 == right
        // 此时 left * left <= x && right * right > x 
        left
    }
        
}

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::cmp::Ordering;

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x < 2 {
            return x;
        }
        
        let mut left = 1;
        let mut right = (x / 2).min(46340) + 1; // 更精确的右边界
        
        while left < right {
            let mid = left + (right - left) / 2;
            match mid.cmp(&(x / mid)) {
                Ordering::Equal => return mid,
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid,
            }
        }
        // 循环结束 left == right
        // 此时 (left - 1)² <= x && right * right > x 
        left - 1
    }
}

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

示例 1：

1
2
3
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

1
2
3
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

  • 1 <= num <= 2^31 - 1

💡 思路：
正整数序列查找x²=num，以1~(x / 2).min(46340) + 1作为区间，判断x²==num返回true否者返回false

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
use std::cmp::Ordering;
impl Solution {
    pub fn is_perfect_square(num: i32) -> bool {
        if num < 1 {
            return false;
        }
        if num == 1 {
            return true;
        }

        let mut left = 1;
        let mut right = (num / 2).min(46340) + 1;

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

            match (middle*middle).cmp(&num) {
                Ordering::Equal => return true,
                Ordering::Less => left = middle + 1,
                Ordering::Greater => right = middle,
            }
        }

        false
    }
}