704. 二分查找

题目描述

给定一个 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

解题思路

直接使用标准库的做法，slice的partition_point没有找到的时候返回数组的长度

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let x = nums.partition_point(|&x| x < target);
        if x == nums.len() { return -1 }
        if nums[x] == target { return x as i32 }
        -1
    }
}
}

手写的二分查找

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid;
            } else {
                return mid as i32
            }
        }
        -1
    }
}
}

学习感想

对区间的定义没有想清楚，区间的定义就是不变量，在操作的过程中 保持不变量

在左闭右闭区间的情况下 由于right 要 -1，所以要考虑right=0 - 1的情况

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0isize;
        let mut right = nums.len() as isize - 1;
        while left <= right {
            let mid = (left + (right - left) / 2) as usize;
            if nums[mid] < target {
                left = mid as isize + 1
            } else if nums[mid] > target {
                right = mid as isize - 1;
            } else {
                return mid as i32
            }
        }
        -1
    }
}
}

重写

• 喜欢用左闭右开的区间
• match arm不需要用,结尾也是合法的语法
• Ordering::Less => { right = mid } 要注意“右开” 又写错了

#![allow(unused)]
fn main() {
struct Solution {}
use std::cmp::Ordering;

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left: usize = 0;
        let mut right: usize = nums.len();
        while left < right {
            let mid: usize = left + (right - left) / 2;
            let mid_num: &i32 = &nums[mid];
            
            match target.cmp(mid_num) {
                Ordering::Equal => { return mid as i32 }
                Ordering::Less => { right = mid }
                Ordering::Greater => { left = mid + 1 }
            }
        }
        -1i32
    }
}

}

使用rust std

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        match nums.binary_search(&target) {
            Ok(idx) => { idx as i32 }
            Err(_) => { -1i32 }
        }
    }
}
}

#![allow(unused)]
fn main() {
struct Solution {}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let idx: usize = nums.partition_point(|&x| x < target);
        if idx == nums.len() { return -1i32 }
        if nums[idx] != target { return -1i32 }
        idx as i32
    }
}

}