龙空技术网

100道高频LeetCode算法图文题解,数组二分一写就废

码科智能 253

前言:

如今姐妹们对“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,如图所示:

递增数组,索引为0和11

注意middle的计算

注意left的变化

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算法题题解