[LeetCode 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

提示

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

题解

题目言简意赅，就是要求使用二分查找思想来解题。那么在此之前，我们需要了解下什么是二分查找。

什么是二分查找？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找的查找过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

使用二分查找需要满足的基础条件

1. 必须采用顺序存储结构。
2. 必须按关键字大小有序排列。

了解了二分查找后，这道题目的解法就呼之欲出了：

AC代码

var search = function(nums, target) {
    let left = 0;
    let right = nums.length;
    while (left <= right) {
        let mid = (left + right) >> 1;
        if (mid >= nums.length) {
            return -1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
};

这就是最最最简单的二分查找的应用啦，不断折中，直到发现满足条件的值。 有没有又get一个查找小技巧！咱们下个题目见啦~

记得不断进步哦~

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情：juejin.cn/post/693314…