[数据结构与算法]Leetcode 高频题解（三）：二分查找（E）

LC704（Easy）. 二分查找（出现次数 Rank3）

题目描述

• 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
• 提示：
  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

举个栗子

• 示例 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。

精彩题解

• 二分查找的做法是，定义查找的范围 $[\text{left},\text{right}]$，初始查找范围是整个数组。
  • 每次取查找范围的中点 $\text{mid}$，比较 $\text{nums}[\text{mid}]$ 和 $\text{target}$ 的大小，如果相等则 $\text{mid}$ 即为要寻找的下标，如果不相等则根据 $\text{nums}[\text{mid}]$ 和 $\text{target}$ 的大小关系将查找范围缩小一半。
  • 由于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是 $O(\log n)$，其中 $n$ 是数组的长度。
• 二分查找的条件是查找范围不为空，即 $\text{left}\le \text{right}$。
  • 如果 $\text{target}$ 在数组中，二分查找可以保证找到 $\text{target}$，返回 $\text{target}$ 在数组中的下标。
  • 如果 $\text{target}$ 不在数组中，则当 $\text{left}>\text{right}$ 时结束查找，返回 -1。

代码来了

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) {
                return mid;
            }else if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        return -1;
    }
}