[leetcode]704-二分查找

有空一起学习 2020年2月9日16:24:04 发表评论

来源:力扣(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-二分查找

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

[leetcode]704-二分查找

三、代码

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

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

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

[leetcode]704-二分查找

本文共执行66次查询,耗时0.345秒!
历史上的今天
二月
9
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: