704. 二分查找

属于 左闭右开的写法

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 = (left + right) / 2;
            if nums[mid] < target {
                left = mid + 1;
            }else if  nums[mid] > target {
                right = mid;
            }else {
                return mid as i32;
            }
        }
        -1
    }
}

左闭右闭的写法 - 比较喜欢使用

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 as i32 <= right as i32{
            let mid = (left + right) / 2;
            if nums[mid] < target {
                left = mid + 1;
            } else if nums[mid] > target {
                right = mid - 1;
            } else {
                return mid as i32;
            }
        }
        -1
    }
}

如果是一个区间的，涉及到 firstIndex 或者 lastIndex 的位置 ，那么就可以加一个 start end 的逻辑 这里也是左闭右闭的另外一个写法

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        while left + 1 < right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] < target {
                left = mid;
            } else if nums[mid as usize] > target {
                right = mid;
            } else {
                right = mid;
            }
        }
 
        // 手动找 first index 或者 last index
        if nums[left as usize] == target {
            return left;
        }
 
        if nums[right as usize] == target {
            return right;
        }
 
        -1
    }
}

#算法/二分