704-二分查找

Doublew2w大约 3 分钟

题目地址(704. 二分查找 - 力扣（LeetCode）)

https://leetcode.cn/problems/binary-search/

题目描述

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

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000] 之间。
nums 的每个元素都将在 [-9999, 9999] 之间。

前置知识

数组

思路

区间定义

当我们选择「左闭右开」的时候，我们可以 0 来定义左边界(left)，而以数组的长度来定义右边界(right)，因此右边界我们是判断不到的。

循环终止条件

在左闭右开的情况，区间不为空，也就意味着 right 至少大于等于 left 。如果超过了这个条件，循环就终止。

判断条件

$nums[mid] == target$ ， $mid$ 就是我们要得到的结果，直接返回
$nums[mid] < target$ ，我们应往右边的区间继续寻找，注意 $mid$ 的位置我们是可以取到的，因此我们更新左边界的时候，应该为 $left = mid +1$
$nums[mid] > target$ ，我们应往左边的区间找，而 $mid$ 的位置明显不是答案，但是我们选择的是左闭右开区间，而右开所指向的位置本身就不在我们的候选区间里，所以 $right = mid$ ，而不是 $right = mid -1$ .
如果 $mid - 1$ 的位置正好是答案，在左闭右开的情况是找不到这个位置的

关键点

左右区间的闭合
左右区间的比较

代码

Java Code:


class Solution {
  public int search(int[] nums, int target) {
      int left = 0;
      int right = nums.length;
      while (left < right){
          int mid = (right + left) / 2;
          if(nums[mid] > target){
              right = mid;
          }else if(nums[mid] < target) {
              left = mid +1 ;
          }else{
              return mid;
          }
      }
      return -1;
}

复杂度分析

令 n 为数组长度。

时间复杂度： $O(logn)$
空间复杂度： $O(1)$

思路改进

在 $nums[mid] < target$ 和 $nums[mid] == target$ 是可以合并起来的。当区间长度为 1 时，剩下的就是答案，由于 nums [mid] 可能等于答案，因此我们不能跳过这个 mid 的位置

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right){
        int mid = (right + left)/2;
        if(nums[mid] > target){
            right = mid;
        }else{
            left = mid;
        }
    }
    if(nums[l] == target){
        return l;
    }
    return -1;
}

左闭右必区间

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right){  // #1
        int mid = (right + left) / 2;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1; // #2
        }else{
            right = mid - 1; // #3
        }
    }
    return -1;
}