leetcode/
search_range.rs

1//! # 34. 在排序数组中查找元素的第一个和最后一个位置
2//!
3//! 难度 中等
4//!
5//! 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
6//!
7//! 如果数组中不存在目标值 target，返回 [-1, -1]。
8//!
9//! ## 进阶：
10//!
11//! 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
12//!
13//!  ## 示例 1：
14//!
15//! ```no_run
16//! /// 输入：nums = [5,7,7,8,8,10], target = 8
17//! /// 输出：[3,4]
18//! use leetcode::search_range::Solution;
19//! assert_eq!(vec![3i32, 4], Solution::search_range(vec![5,7,7,8,8,10], 8));
20//! ```
21//!
22//! ## 示例 2：
23//!
24//! ```no_run
25//! /// 输入：nums = [5,7,7,8,8,10], target = 6
26//! /// 输出：[-1,-1]
27//! use leetcode::search_range::Solution;
28//! assert_eq!(vec![-1i32, -1], Solution::search_range(vec![5,7,7,8,8,10], 6));
29//! ```
30//!
31//! ## 示例 3：
32//!
33//! ```no_run
34//! /// 输入：nums = [], target = 0
35//! /// 输出：[-1,-1]
36//! use leetcode::search_range::Solution;
37//! assert_eq!(vec![-1i32, -1], Solution::search_range(vec![], 0));
38//! ```
39//!
40//! ## 提示：
41//!
42//! * `0 <= nums.length <= 105`
43//! * `-109 <= nums[i] <= 109`
44//! * nums 是一个非递减数组
45//! * `-109 <= target <= 109`
46//!
47//! See [leetcode](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
48pub struct Solution;
49impl Solution {
50
51    /// 二分法，找到 target 的 lower 和 high 边界
52    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
53        match (binary_search_low(&nums[..], target), binary_search_high(&nums[..], target)) {
54            (Some(lower), Some(upper)) => vec![lower as i32, upper as i32],
55            _ => vec![-1, -1],
56        }
57    }
58}
59
60// TODO
61fn binary_search_low(nums: &[i32], target: i32) -> Option<usize> {
62    let mut len = nums.len();
63    if len == 0 {
64        return None;
65    } else if len == 1 && nums[0] == target {
66        return Some(0);
67    }
68    let mut base = 0;
69    let mut res = None;
70
71    while len > 1 {
72        let half = len / 2;
73        let mid = base + half;
74        if len == 2 {
75            if nums[base] == target {
76                return Some(base);
77            } else if nums[mid] == target {
78                return Some(mid);
79            }
80        }
81        base = if nums[mid] >= target {
82            res = Some(mid);
83            base
84        } else {
85            mid
86        };
87        len -= half;
88    }
89    res.and_then(|r| {
90        if nums[r] == target {
91            Some(r)
92        } else {
93            None
94        }
95    })
96}
97
98fn binary_search_high(nums: &[i32], target: i32) -> Option<usize> {
99    let mut len = nums.len();
100    if len == 0 {
101        return None;
102    } else if len == 1 && nums[0] == target {
103        return Some(0);
104    }
105
106    let mut base = 0;
107    let mut res = None;
108
109    while len > 1 {
110        let half = len / 2;
111        let mid = base + half;
112
113        if len == 2 {
114            if nums[mid] == target {
115                return Some(mid);
116            } else if nums[base] == target {
117                return Some(base);
118            }
119        }
120
121        base = if nums[mid] > target {
122            res = Some(base);
123            base
124        } else {
125            mid
126        };
127        len -= half;
128    }
129    res.and_then(|r| {
130        if nums[r] == target {
131            Some(r)
132        } else {
133            None
134        }
135    })
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    #[test]
143    fn test() {
144        let t = |n, t| Solution::search_range(n, t);
145        assert_eq!(vec![3i32, 4], t(vec![5,7,7,8,8,10], 8));
146        assert_eq!(vec![-1i32, -1], t(vec![5,7,7,8,8,10], 6));
147    }
148}
leetcode/search_range.rs

leetcode/
search_range.rs
