写点什么

算法突破:二分查找

作者:掘金安东尼
  • 2022 年 10 月 05 日
    广西
  • 本文字数:714 字

    阅读完需:约 2 分钟

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的,Level 1 和 Level 2 学习计划是为初级用户和中级用户准备的,题目覆盖了大多数中层公司面试时所必需的数据结构和算法,Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源

第 7 天

二分查找

给定一个 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
复制代码

题解

题目很直接,二分法查找目标值:


将数组一分为二,看看目标值是大于中间值,还是小于中间值,如果是大于中间值,那说明目标值在分组 2 里面,如果小于中间值,则在分组 1 里面。


JavaScript 实现:


var search = function(nums, target) {    //先求出中间需要是多少    let left = 0, right = nums.length - 1;    while (left <= right) {// 当左序号小于右序号,进入条件执行        const mid = Math.floor((right - left) / 2) + left; // 中间需要等于        const num = nums[mid]; // 取中间数值        if (num === target) { // 如果等于,则 return            return mid;        } else if (num > target) { // 如果大于,则缩小右指针            right = mid - 1;        } else { // 如果小于,则缩小左指针            left = mid + 1;        }    }    return -1;};
复制代码

总结

真的是:简单题重拳出击,中等题翻找手套,困难题铺好床垫~

发布于: 刚刚阅读数: 4
用户头像

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

真正的大师,永远怀着一颗学徒的心(易)

评论

发布
暂无评论
算法突破:二分查找_算法_掘金安东尼_InfoQ写作社区