前言:
如今姐妹们对“leetcode算法题题解”都比较重视,看官们都需要知道一些“leetcode算法题题解”的相关内容。那么小编也在网摘上搜集了一些对于“leetcode算法题题解””的相关内容,希望姐妹们能喜欢,各位老铁们快快来了解一下吧!在这个系列的博客中,我们根据LeetCode官方给出的每个题目的出现频率,整理并收录了每个类别里高频出现的题目,从简单到中等再到困难,为你提供解题技巧和最佳实践。我们将介绍常见的算法思想,如贪心算法、动态规划、回溯算法等,希望能帮助你提高算法水平,成为你进入人工智能行业敲门砖。
704:二分查找(难度2/频率5)
题目链接:
给定一个 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
解题思路
本题提到数组为有序数组,同时还强调无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。
大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要不信你现在可以动手写个二分查找,一定会遇到一个问题,到底是 while(left < right) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
二分查找的区间是不断迭代的,解决上述问题就一定要遵循区间定义,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。
第一种写法:区间左闭右闭
区间的定义决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:
while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在下列数组查找元素33,如图所示:
class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 # 定义target在左闭右闭的区间里,[left, right] while left <= right: middle = left + (right - left) // 2 if nums[middle] > target: right = middle - 1 # target在左区间,所以[left, middle - 1] elif nums[middle] < target: left = middle + 1 # target在右区间,所以[middle + 1, right] else: return middle # 数组中找到目标值,直接返回下标 return -1 # 未找到目标值第二种写法:区间左闭右开
区间左闭右开,也就是[left, right) ,那么二分法的边界处理方式则截然不同。
有如下两点:
while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的;if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle;
比如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:
class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) # 定义target在左闭右开的区间里,即:[left, right) while left < right: # 因为left == right的时候,在[left, right)是无效的空间,所以使用 < middle = left + (right - left) // 2 if nums[middle] > target: right = middle # target 在左区间,在[left, middle)中 elif nums[middle] < target: left = middle + 1 # target 在右区间,在[middle + 1, right)中 else: return middle # 数组中找到目标值,直接返回下标 return -1 # 未找到目标值题目总结
二分法是非常重要的基础算法,理解清楚区间的定义,从而更准确的处理边界情况,其时间复杂度为(O (log2n )),再通过一个动图让你加深对二分法的理解。
相关题目推荐35.搜索插入位置34. 在排序数组中查找元素的第一个和最后一个位置69. x 的平方根367.有效的完全平方数
标签: #leetcode算法题题解