首页 > 其他分享 >Leetcode刷题笔记——二分法

Leetcode刷题笔记——二分法

时间:2023-09-02 15:56:27浏览次数:43  
标签:right target nums 二分法 middle 查找 刷题 Leetcode left

二分法是搜索算法中极其典型的方法,其要求输入序列有序并可随机访问。算法思想为

输入:有序数组nums,目的数值target
要求输出:如果target存在在数组中,则输出其index,否则输出-1

  1. 将原数组通过[left,right]两个索引划分范围,初值left=0,right=数组的最后一个元素
  2. 当left <= right时
    1. middle = (left + right)/2
    2. 判断nums[middle]是不是要查找的target,如果是则返回结果
    3. 判断nums[middle]> target,证明要查找的target在左边,因此right = middle - 1
    4. 判断nums[middle]< target,证明要查找的target在右边,因此left = middle + 1
  3. 没有查找到return -1。

形如下图:

传统的二分法代码如下:

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return -1
}

这里要注意两个问题:

  1. 上述算法中的第2步中=的判断,即for left <= right还是for left < right
  2. 上述算法2.2-2.4中的判断条件以及下一次查找区间的设置
  3. 返回值代表什么意思

for left<= right 中 = 的判断

首先对于第一个问题,=是否应该存在,取决于对于二分查找的初始化定义,例如:

  1. 如果二分查找遍历的区间采用[left,right](数学中的双闭区间)的形式,考虑left==right=成立的情况,则表示区间内只有单个操作数,这种情况还是需要处理,否则无法通过其余方式表示这种情况,所以此时=是必须的。
  2. 如果二分查找遍历的区间采用[left,right)的形式,考虑left==right=成立的情况,事实证明,这种情况并不应该存在,我们无法用[i,i)表示任何一个区间,所以,这种情况下,=就不是必须的。

判断条件以及下一次查找区间的设置

然后考察对于第二个问题,判断条件以及下一次查找区间应该如何设置

注意:二分查找是一个经典的查找算法,其目的是查找到指定的位置或者值,并不仅限于查找到等于target的index这一种情况。

但无论怎样,二分查找本身有一个固定模式,即二分,就是从middle处将区间[left,right]分成两份,然后根据middle的情况查找(或者更新新的区间),因此,我们只需要考虑清楚如下三种条件时要怎么处理即可:

  1. 当遍历到nums[middle] == target时应该怎样处理(新的查找区间是什么),即当前值等于目标值
  2. 当遍历到nums[middle] > target时应该怎样处理(新的查找区间是什么),即当前值大于目标值
  3. 当遍历到nums[middle] < target时应该怎样处理(新的查找区间是什么),即当前值小于目标值

讨论完上述两个问题,其实二分法就有了一个固定的框架:

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			// 当前值等于目标值时,如何处理(新的查找区间是什么)
		} else if nums[middle] > target {
			// 当前值大于目标值时,如何处理(新的查找区间是什么)
		} else {
			// 当前值小于目标值时,如何处理(新的查找区间是什么)
		}
	}
    // 考虑返回值的意义
	return 
}

返回值的含义

最后我们讨论返回值的含义这一话题。在传统的二分查找中,只有在两种情况下会返回:

  1. 查找到目标target,返回查找到的index
  2. 未查找到目标target,返回-1。(即文章最起始处 步骤3的含义)

这里返回值的含义表示target在nums中的index,该值只会出现在nums[middle]==target这一条件下。然而,刚才提到了二分查找不总是处理等式条件,因此我们总要思考两种返回值的含义:

  1. nums[middle]==target,这时return代表的是什么?
  2. 数组中不存在target,此时return的是什么,此时left、right代表什么?

这里我们举一个稍稍复杂一点的例子对二分查找进行分析。

搜索插入位置

题目要求如下:

这个问题要求返回两种返回值:

  1. 在数组中找到目标值,并返回其索引
  2. 如果目标值不存在于数组中,返回它将会被按顺序插入的位置

其中对于情况1,传统的二分查找算法就可以解决,而情况2,则需要借助于本部分要讲解的返回值的含义

对于传统的二分法:

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return -1
}

如果target能在nums数组中查找到,必定最终查找到一个[i,i]类型的区间,即区间中只有一个数字,否则区间就要再次进行二分。例如:如果要在下列数组中查找4所在的位置,查找过程如下,第三步时,查找区间为[2,3],有两个值,无法确定答案,则需要再次进行一次查找:

target == 4
nums   1  2  3  4
index  0  1  2  3
1      l        r
2         l     r
3            l  r
4               lr 

那么最终我们处理的情况必定是对于区间[left,right]中,其中left == right,因此middle == left == right,此时nums[middle]和target的关系。

  • nums[middle] > target,则需要从middle左侧继续寻找,right = middle - 1,注意此时left = middle,left > right
  • nums[middle] < target,则需要从middle右侧继续寻找,left = middle + 1,注意此时right = middle,left > right

所以此时,left指向的永远是大的那个值,right是小的那个值(因为left <= right时,循环不会终止,循环终止条件为left > right,根据数组的有序性,nums[left] > nums[right])。

最后,我们考察该题,对于数组nums,如果目标值不在其中,那么其最终查找到的值只有两种情况:

  1. nums[middle] < target,此时nums[middle]应该是第一个小于target的值,如果要查找target所在位置,应该返回大于middle的index,即left
  2. nums[middle] > target,此时nums[middle]应该是第一个大于target的值,如果要查找target所在位置,应该返回等于middle的index,用target替换middle位置的值,即left

因此,该题的结果,只需要修改传统二分查找的最后一行:

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			return middle
		} else if nums[middle] > target {
			right = middle - 1
		} else {
			left = middle + 1
		}
	}
	return left 
}

在排序数组中查找元素的第一个和最后一个位置

题目要求如下:

注意这里查找的是元素第一次和最后一次出现的位置,这里我们以查找第一次出现的位置举例,后者同理。

考察我们在判断条件以及下一次查找区间的设置中强调的,考察二分查找的三种情况:

情况 分析 操作
nums[middle] == target时,即当前值等于目标值 第一次出现的位置可能在当前值前面 right = middle - 1
nums[middle] > target时,即当前值大于目标值 第一次出现的位置在当前值前面 right = middle - 1
nums[middle] < target时,即当前值小于目标值 第一次出现的位置在当前值后面 left = middle + 1

与之前不同的是当nums[middle] == target时,不再有返回值了,那么考虑最后返回值的含义,最终left > right时情况有如下3种:

情况 分析 操作
nums[middle] == target 此时,middle前的值必定<middle,而不是等于(只要等于,考虑上表的情况1,会使right = middle - 1) return left
nums[middle] > target 此情况不存在,因为如果有这种情况会继续使right=middle-1 不进行操作
nums[middle] < target 此时middle必定是target前的第一个元素 return left

经过上面的分析后,可以清晰的写出代码:

    l, r := 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] >= target {
			r = m - 1
		} else {
			l = m + 1
		}
	}
    result := l

而查找元素出现的最后一个位置,只需要反过来,最后return right即可。代码如下:

    l, r: = 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] <= target {
			l = m + 1
		} else {
			r = m - 1
		}
	}
    result := r

总结

本文详细分析了二分查找的所有细节,对于二分查找处理的问题,我们常常需要更加关注本文讨论的后两个问题:

  1. 判断条件以及下一次查找区间的设置
  2. 返回值的含义

最后填充模版即可。

func binarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		middle := (left + right) / 2
		if nums[middle] == target {
			// 当前值等于目标值时,如何处理(新的查找区间是什么)
		} else if nums[middle] > target {
			// 当前值大于目标值时,如何处理(新的查找区间是什么)
		} else {
			// 当前值小于目标值时,如何处理(新的查找区间是什么)
		}
	}
    // 考虑返回值的意义
	return 
}

标签:right,target,nums,二分法,middle,查找,刷题,Leetcode,left
From: https://www.cnblogs.com/yanlishao/p/17673640.html

相关文章

  • LeetCode952三部曲之一:解题思路和初级解法(137ms,超39%)
    欢迎访问我的GitHub这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos题目描述难度:困难编程语言:Java给定一个由不同正整数的组成的非空数组nums,考虑下面的图:有nums.length个节点,按从nums[0]到nums[nums.length-1]标记;只有当......
  • 前端歌谣的刷题之路-第七题-语义化标签
    目录前言题目编辑核心代码总结前言我是歌谣歌谣的意志是永恒的放弃很容易但是坚持一定很酷本题目源自于牛客网题目请使用语义化标签创建头部标签且包含导航标签。注意:只需在html模块填写标签结构,有且仅有一个头部标签和一个导航标签编辑核心代码```语义化标签```......
  • 【刷题笔记】31. Next Permutation
    题目Implement nextpermutation,whichrearrangesnumbersintothelexicographicallynextgreaterpermutationofnumbers.Ifsuchanarrangementisnotpossible,itmustrearrangeitasthelowestpossibleorder(i.e.,sortedinascendingorder).Thereplac......
  • [LeetCode][416]partition-equal-subset-sum
    ContentGivenanintegerarraynums,returntrueifyoucanpartitionthearrayintotwosubsetssuchthatthesumoftheelementsinbothsubsetsisequalorfalseotherwise. Example1:Input:nums=[1,5,11,5]Output:trueExplanation:Thearraycanb......
  • [LeetCode][494]target-sum
    ContentYouaregivenanintegerarraynumsandanintegertarget.Youwanttobuildanexpressionoutofnumsbyaddingoneofthesymbols'+'and'-'beforeeachintegerinnumsandthenconcatenatealltheintegers.Forexample,if......
  • leetcode & c++多线程刷题日志
    1.按序打印按序打印解法互斥锁classFoo{mutexmtx1,mtx2;public:Foo(){mtx1.lock(),mtx2.lock();}voidfirst(function<void()>printFirst){printFirst();mtx1.unlock();}voidsecond(function<voi......
  • Leetcode刷题笔记——单调性
    单调性单调性是数学中使用的一种常见性质,通常用于描述函数,在高等数学中的定义常常为:设函数f(x)在区间I上有定义,如果对于I上的任意两个数x1和x2,当x1<x2时,有f(x1)<f(x2)(或者f(x1)>f(x2)),则称函数f(x)在区间I上是单调递增的(或者单调递减的)。例如如下图像就是两个单调函数。利用单......
  • 刷题记录(五)
    攻防世界-bug启动环境发现有登陆、注册、找回密码三个功能随便注册一个用户登陆以后,点击管理发现后台做了检测,非admin不让用在初始界面有一个findpwd的链接,发现修改密码的时候会携带用户名,尝试将用户名改成admin看是否存在越权改成admin,成功修改,再用admin账号进行登陆。......
  • 平时刷题遇到的一些常见问题
    文章目录1、头文件2、输入多组数据(未知长度)3、常见的输出方式(1)整体输出(2)反向输出(3)控制输出精确度(4)输出后面无空格(vector)(5)list不能随机访问,可以转换为vector输出(6)可以先输出首元素,后面在输出元素前先加上空格4、结构体入栈有几个注意事项5、堆栈溢出的几个问题6、关于返回值的问......
  • 剑指offer刷题总结
    文章目录一、数组二、链表三、栈和队列四、二叉树五、字符串六、回溯算法七、其他一、数组01、二维数组中的查找06、旋转数组的最小数字12、调整数组顺序使奇数位于偶数前面27、数组中出现次数超过一半的数字29、连续子数组的最大和31、把数组排成最小的数34、数组中的逆序对36、......