环球资源网商务网站建设目的,2023年营业执照年检申报,怎么用phpcmf做网站,wordpress 全局置顶每日一题#xff1a;LeetCode704.二分查找 LeetCode704.二分查找知识点#xff1a;二分法解题代码 LeetCode704.二分查找
问题描述#xff1a;给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中… 每日一题LeetCode704.二分查找 LeetCode704.二分查找知识点二分法解题代码 LeetCode704.二分查找
问题描述给定一个 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]之间。
知识点二分法 定义二分查找算法也称折半搜索算法对数搜索算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半时间复杂度是log(n) 一是有序数组这里可能是整体有序比如[1,2,3,4,5]也有可能是局部有序比如[4,5,1,2,3]二是特定元素也有可能是满足特定的条件。由定义我们大概就知道了二分法的应用场景在有序数组中找特定值都可以考虑用二分法 二分法的步骤 我们要在一组升序的数组找一个数的下标那我们肯定是先拿中间的与他进行比较比较大小的判断其实就相当于是这个性质且这个 性质满足二段性将大于和小于我们要查找的值分为两段而我们的查找结果就是分界点 二分法的使用条件①上下界确定 ②区间内有序也可以是局部有序
解题
思路①这道题目的前提是数组为有序数组同时题目还强调数组中无重复元素因为一旦有重复元素使用二分查找法返回的元素下标可能不是唯一的这些都是使用二分法的前提条件②二分查找涉及的很多的边界条件逻辑比较简单但就是写不好。例如到底是 while(left right) 还是 while(left right)到底是right middle呢还是要right middle - 1呢③写二分法区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。 第一种写法定义 target 是在一个在左闭右闭的区间里也就是[left, right] 这个很重要非常重要。 区间的定义这就决定了二分法的代码应该如何写因为定义target在[left, right]区间所以有如下两点 while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1 例如在数组1,2,3,4,7,9,10中查找元素2如图所示 第二种方法 如果说定义 target 是在一个在左闭右开的区间里也就是[left, right) 那么二分法的边界处理方式则截然不同。 有如下两点 while (left right)这里使用 ,因为left right在区间[left, right)是没有意义的if (nums[middle] target) right 更新为 middle因为当前nums[middle]不等于target去左区间继续寻找而寻找区间是左闭右开区间所以right更新为middle即下一个查询区间不会去比较nums[middle] 在数组1,2,3,4,7,9,10中查找元素2如图所示注意和方法一的区别
代码
python版本一左闭右闭区间
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1 # 定义target在左闭右闭的区间里[left, right]while left right:mid (left right)/2if 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 # 未找到目标值python版本二左闭右开区间
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)是无效的空间所以使用 mid (left right)/2if nums[middle] target:right middle # target 在左区间在[left, middle)中elif nums[middle] target:left middle 1 # target 在右区间在[middle 1, right)中else:return middle # 数组中找到目标值直接返回下标return -1 # 未找到目标值C版本一左闭右闭区间
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size() - 1; // 定义target在左闭右闭的区间里[left, right]while (left right) { // 当leftright区间[left, right]依然有效所以用 int middle (left right)/2;// 防止溢出 等同于(left right)/2if (nums[middle] target) {right middle - 1; // target 在左区间所以[left, middle - 1]} else if (nums[middle] target) {left middle 1; // target 在右区间所以[middle 1, right]} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};C版本二左闭右开区间
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size(); // 定义target在左闭右开的区间里即[left, right)while (left right) { // 因为left right的时候在[left, right)是无效的空间所以使用 int middle (left right)/2;if (nums[middle] target) {right middle; // target 在左区间在[left, middle)中} else if (nums[middle] target) {left middle 1; // target 在右区间在[middle 1, right)中} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};
