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 in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

Note:

  1. You may assume that all elements in nums are unique.
  2. n will be in the range [1, 10000].
  3. 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.