1. 二分查找详解

点击这里查看力扣标题，了解详细信息。

当你面对一个升序排列的整数数组 nums 并寻觅一个特定目标值 target 时，你可以选用一种高效的查找办法来定位这个目标值。假如目标值存在于数组中，那么就回来它的索引；假如不存在，就回来 -1 作为标记。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
阐明: 目标值 9 在数组中的索引为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
阐明: 目标值 2 并不在数组中，因此回来 -1

提示：

  • 数组 nums 中的元素是仅有的。
  • 数组的巨细 n 范围在 [1, 10000]。
  • 数组元素的值域是 [-9999, 9999]。

办法探求

此题假定数组是有序且无重复元素的，这为二分查找供给了抱负的应用条件。但是，要正确完成二分查找，关键在于如何处理查找的边界条件，这往往是编码时最容易犯错的地方。主要有两种方式来定义查找区间：左闭右闭 [left, right] 和左闭右开 [left, right)。

二分查找的完成办法

  • 选用左闭右闭区间 [left, right]：

    • 循环条件运用 while (left <= right)，意味着 left 和 right 持平是有用的，需要被检查。
    • 假如发现 nums[middle] > target，则阐明 target 不可能是 nums[middle]，下一步 right 应该调整到 middle - 1。
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left, mut right) = (0_i32, nums.len() as i32 - 1);
        while left <= right {
            let mid = (left + right) / 2;
            match nums[mid as usize].cmp(&target) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid - 1,
                Ordering::Equal => return mid,
            }
        }
        -1
    }
}

  • 选用左闭右开区间 [left, right)：

    • 循环条件改为 while (left < right)，由于当 left 和 right 持平时，区间不再有用。

    • 假如 nums[middle] > target，那么 right 更新为 middle，由于 nums[middle] 现已被排除在外，接下来的查找区间应该是左闭右开的 [left, middle)。

use std::cmp::Ordering;
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let (mut left, mut right) = (0_i32, nums.len() as i32);
        while left < right {
            let mid = (right + left) / 2;
            match nums[mid as usize].cmp(&target) {
                Ordering::Less => left = mid + 1,
                Ordering::Greater => right = mid,
                Ordering::Equal => return mid,
            }
        }
        -1
    }
};
  • 时间复杂度： 对于两种办法而言，都是 O(log n)，由于每次查找都是将查找区间缩小到原来的一半。
  • 空间复杂度： O(1)，我们只需要常数等级的额外空间。

深化了解二分查找

二分查找，作为一个经典而高效的查找算法，之所以可以在有序数组中快速定位元素，是由于它每一步都将待查找的区间减半，然后大幅减少了查找所需的时间。但是，恰当地完成二分查找并非毫无应战。许多时分，我们可能会遇到各种边界条件的处理问题，导致写出来的代码不符合要求，但是实际上，搞明白边界问题，二分查找就是手拿把掐，手到擒来！Pomelo_刘金，转载请注明原文链接。感谢！