当前位置:网站首页>704 二分查找
704 二分查找
2022-07-06 08:22:00 【故、梦】
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
提示:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
思路
对于在有序无重复数组中查找目标值的问题,可以考虑二分查找来实现。
题目中说到,nums 中的所有元素是不重复的,且 nums 按升序排列,所以可以考虑使用二分查找法。
二分查找的逻辑比较简单,但在边界条件的处理上很容易出错。例如,我们写 while(left < right)
和 while(left <= right)
对应的处理方式就完全不同。
举一个简单的例子,假设数组中只有一个元素 5,目标值 target
也等于 5。如果使用 while(left < right)
的写法,那么 right
就应该初始化为 1,left
初始化为 0。而如果使用 while(left <= right)
写法,left
和 right
都应初始化为 0。所以两种写法的不同就在于边界条件的处理。
所以根据边界条件的处理方式,二分查找有以下两种写法。
第一种写法
假设数组元素是 [1,2,3,4,5,6,7]
,target = 3
,我们使用 while(left < right)
写法实现二分排序。
这种写法里,left = 0,right = 7
,运算过程如图所示
代码的关键在于,当 nums[mid] < nums[right]
时,right = mid
。循环中 right
是开区间,这里也应是开区间,保持一致。
对应的代码如下:(Kotlin)
class Solution {
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size // [left,right) 右侧为开区间,right 设置为 nums.size
while (left < right) {
val mid = (left + right) / 2
if (nums[mid] < target) left = mid + 1
else if (nums[mid] > target) right = mid // 代码的核心,循环中 right 是开区间,这里也应是开区间
else return mid
}
return -1 // 没有找到 target ,返回 -1
}
}
第二种写法
假设数组元素是 [1,2,3,4,5,6,7]
,target = 3
,我们使用 while(left <= right)
写法实现二分排序。
这种写法里,`left = 0,right = 76,运算过程如图所示
代码的关键在于,当 nums[mid] < nums[right]
时,right = mid - 1
。循环中 right
是闭区间,这里也应是闭区间,保持一致。
对应的代码如下:(Kotlin)
class Solution {
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1 // [left,right] 右侧为闭区间,right 设置为 nums.size - 1
while (left <= right) {
val mid = (left + right) / 2
if (nums[mid] < target) left = mid + 1
else if (nums[mid] > target) right = mid - 1 // 代码的核心,循环中 right 是闭区间,这里也应是闭区间
else return mid
}
return -1 // 没有找到 target ,返回 -1
}
}
边栏推荐
- Migrate data from SQL files to tidb
- Mobile Test Engineer occupation yyds dry goods inventory
- Convolution, pooling, activation function, initialization, normalization, regularization, learning rate - Summary of deep learning foundation
- sys.argv
- 使用 BR 恢复 S3 兼容存储上的备份数据
- Résumé des diagrammes de description des broches de la série ESP
- Hcip day 16
- 使用 TiUP 升级 TiDB
- Migrate data from CSV files to tidb
- 备份与恢复 CR 介绍
猜你喜欢
Personalized online cloud database hybrid optimization system | SIGMOD 2022 selected papers interpretation
Online yaml to CSV tool
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
Fibonacci sequence
Pointer advanced --- pointer array, array pointer
Synchronized solves problems caused by sharing
Online yaml to CSV tool
wincc7.5下载安装教程(Win10系统)
【MySQL】锁
[research materials] 2022 enterprise wechat Ecosystem Research Report - Download attached
随机推荐
CAD ARX gets the current viewport settings
3. File operation 3-with
Asia Pacific Financial Media | "APEC industry +" Western Silicon Valley invests 2trillion yuan in Chengdu Chongqing economic circle to catch up with Shanghai | stable strategy industry fund observatio
Day29-t77 & t1726-2022-02-13-don't answer by yourself
Nacos Development Manual
【MySQL】数据库的存储过程与存储函数通关教程(完整版)
2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers
Golang DNS 随便写写
Introduction to backup and recovery Cr
[research materials] 2021 Research Report on China's smart medical industry - Download attached
Hungry for 4 years + Ali for 2 years: some conclusions and Thoughts on the road of research and development
Ruffian Heng embedded bimonthly, issue 49
All the ArrayList knowledge you want to know is here
NFT smart contract release, blind box, public offering technology practice -- contract
Verrouillage [MySQL]
From monomer structure to microservice architecture, introduction to microservices
升级 TiDB Operator
使用 TiDB Lightning 恢复 S3 兼容存储上的备份数据
Colorlog combined with logging to print colored logs
指针和数组笔试题解析