##
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
题解
笨比版本
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
|
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
if nums.len() == 0 {
return -1;
}
let mut left = 0;
let mut right = nums.len() - 1;
let mut mid = nums.len() / 2;
while left <= right {
if left == right {
if nums[left] == target {
return left as i32;
} else {
return -1;
}
}
let c = *nums.get(mid).unwrap();
if c == target {
return mid as i32;
} else if c < target {
left = mid + 1;
mid = (left + right) / 2
} else {
right = mid - 1;
mid = (left + right) / 2
}
}
-1
}
}
|
优化过后版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -> i32 {
let mut left: usize = 0;
let mut right: usize = nums.len() - 1;
while left < right {
let mid = (left + right) / 2;
if nums[mid] < target {
left = mid + 1;
} else if nums[mid] > target {
right = mid;
} else {
return mid as i32;
}
}
-1
}
}
|
思路
最主要的困难点在于边界问题的处理
以前一直有这个问题，不过是用的弱类型的语言，所以一直没啥问题
这次用 rust 写，i32 跟 usize 一个有符号，一个无符号，导致在第一个版本的时候，写了很多冗余代码处理这个问题。
然后发现边界处理，可以在循环外层解决，左闭右开的方式
来源