704. Binary Search
Given a sorted (in ascending order) integer array nums
of n
elements and a target
value, write a function to search target
in nums
. If target
exists, then return its index, otherwise return -1
.
Example 1:
Input:nums
= [-1,0,3,5,9,12],target
= 9 Output: 4 Explanation: 9 exists innums
and its index is 4
Example 2:
Input:nums
= [-1,0,3,5,9,12],target
= 2 Output: -1 Explanation: 2 does not exist innums
so return -1
Note:
- You may assume that all elements in
nums
are unique. n
will be in the range[1, 10000]
.- The value of each element in
nums
will be in the range[-9999, 9999]
.
Rust Solution
struct Solution;
use std::cmp::Ordering::*;
impl Solution {
fn search(nums: Vec<i32>, target: i32) -> i32 {
let n = nums.len();
let mut l: usize = 0;
let mut r: usize = nums.len() - 1;
while l <= r {
let mid = (l + r) / 2;
match nums[mid].cmp(&target) {
Equal => {
return mid as i32;
}
Less => {
if mid + 1 > n - 1 {
break;
}
l = mid + 1;
}
Greater => {
if mid < 1 {
break;
}
r = mid - 1;
}
}
}
-1
}
}
#[test]
fn test() {
let nums = vec![-1, 0, 3, 5, 9, 12];
let target = 9;
assert_eq!(Solution::search(nums, target), 4);
let nums = vec![-1, 0, 3, 5, 9, 12];
let target = 2;
assert_eq!(Solution::search(nums, target), -1);
}
Having problems with this solution? Click here to submit an issue on github.