当前位置: 首页 > news >正文

leetcode 704. 二分查找

  • 题目描述
  • 解题思路
  • 执行结果
leetcode 704. 二分查找


题目描述

  1. 二分查找

给定一个 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

提示:

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

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

法1

方法1:二分法
题目已经描述得很清楚了,使用二分法查找数,二分法也非常适用于这种排序的数组,对时间有很多优化

具体实现方法如下:

我们使用二分查找算法来搜索目标值。

  1. 首先,我们将数组的左边界 left 设置为 0,右边界 right 设置为数组长度减 1。
  2. 然后,我们在每一步迭代中计算中间元素的下标 mid。如果 nums[mid] 等于目标值 target,则返回 mid。如果 nums[mid] 小于目标值 target,则更新 left 为 mid + 1,表示目标值可能在右半部分。如果 nums[mid] 大于目标值 target,则更新 right 为 mid - 1,表示目标值可能在左半部分。当 left 大于 right 时,表示目标值不存在于数组中,因此返回 -1。
  • 时间复杂度(O(logn))
  • 空间复杂度(O(1))

执行结果

法1

func search(nums []int, target int) int {
 left, right := 0len(nums)-1

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

 return -1
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 20 ms , 在所有 Go 提交中击败了 99.64% 的用户 内存消耗: 6.5 MB , 在所有 Go 提交中击败了 69.89% 的用户 通过测试用例: 47 / 47 炫耀一下:

法2


法3


本文由 mdnice 多平台发布

http://www.lryc.cn/news/66486.html

相关文章:

  • 蓝牙耳机什么牌子好?500内好用的蓝牙耳机推荐
  • 设计模式 -- 中介者模式
  • 人工智能的未来之路:语音识别的应用与挑战
  • c++ 友元介绍
  • 四维轻云地理空间数据在线管理软件能够在线管理哪些数据?
  • 学习 GitHub 对我们有什么好处?
  • java记录-反射
  • 这次彻底不需要账号了,无需魔法永久白嫖GPT
  • 远程桌面连接是什么?如何开启远程桌面连接详细教程
  • lua实战(2)
  • UI自动化测试案例——简单的Google搜索测试
  • C++之虚函数原理
  • Windows Information Protection(WIP)部署方案
  • 细说Hibernate的缓存机制
  • 初识C++之线程库
  • ChatGLM-LLaMA-chinese-insturct 学习记录(含LoRA的源码理解)
  • JuiceFS-K8s部署
  • 2023最新版本Camtasia电脑录屏软件好不好用?
  • 第三章 Linux 初步
  • linux环境安装使用mysql详解
  • SUNTANS模型学习(9)——学习Tidal forcing算例
  • ​力扣解法汇总1010. 总持续时间可被 60 整除的歌曲
  • 利用老毛桃pe启动U盘启动ubuntu.iso,完成ubuntu系统的安装
  • 分享2个教学视频录制的方法!
  • 「SQL面试题库」 No_63 报告的记录 II
  • 【事务】怎么去理解事务?
  • camunda流程变量如何使用
  • CMIP6:WRF模式动力降尺度、单点降尺度、统计方法区域降尺度
  • 2023建筑设计师们有哪些好用的AI设计工具?
  • mysql主从复制与读写分离