[leetcode]704-二分查找

马谦马谦马谦 数据结构和算法评论183字数 886阅读 2 分 57 秒阅读模式

来源:力扣 (LeetCode)

链接:https://leetcode-cn.com/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

提示:

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

二、二分查找

二分查找的前提要求是数组有序,一趟二分查找的算法描述为:

  1. 确定数组上下边界,然后取中间值 mid 。
  2. 对比中间值 mid 和目标值 target,此时有两种情况:
    • 如果 target 小于 mid,说明目标值在下边界区,继续在下半边界执行步骤 1 。
    • 如果 target 大于 mid,说明目标值在上边界区,继续在上半边界执行步骤 1 。
  3. 如果上下边界一直找完都没有找到目标值,说明数组中不存在指定数据。

图文描述

在数组 [2, 3, 4, 5, 6, 7, 8] 中查找 3 。第一步,计算 mid 是下标为 3 的值 5,此时 5 比目标值 3 要大,说明 3 出现在 5 左边,要在 [low, mid) 进行下一步查找:

[leetcode]704-二分查找-图片1

第二步,重新定位修改区域,查找的下标范围是 [0, 2] 。此时 mid 计算出来等于 1,下标等于 1 的元素值为 3,刚好就是我们要找的目标值,查找完成:

[leetcode]704-二分查找-图片2

三、代码

需要注意的点已经在代码中标出:

  1. 注意有符号、无符号以及数据是否会溢出。当前题目中数据不大,所以直接使用 int 。
  2. 循环结束的条件是 low > high,所以循环条件一定是 low <= high,不要少了等于符号。
  3. 没有找到目标值的时候,返回-1 。

这么简单的一个题目,提交了 4 次才通过。。。。基础很重要!!!

[leetcode]704-二分查找-图片3

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020 年 2 月 9 日 16:24:04
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/leetcode704-binary-search.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证