那个网站做国外售货,做电子商务网站的意义,邯郸房地产网站建设,制作视频用什么app文章目录 1.二分搜索法1.1什么是二分搜索法#xff1f;1.2解法思路1.3扩展 1.二分搜索法
题目原文#xff1a;
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值… 文章目录 1.二分搜索法1.1什么是二分搜索法1.2解法思路1.3扩展 1.二分搜索法
题目原文
给定一个 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 中因此返回 -11.1什么是二分搜索法
我们来看AI给出的回答 二分搜索法又称折半查找算法是一种在有序列表如数组中高效查找特定元素的搜索算法。该算法利用了列表元素已排序的特性通过反复将待搜索区间分成两半来缩小查找范围具体步骤如下 初始化: 确定搜索区间通常开始时是整个列表设两个指针分别指向列表的起始位置low和结束位置high。 计算中间位置: 计算当前搜索区间的中间索引 mid (low high) / 2并获取该位置的元素值。 比较与决策: 如果中间元素正好是要查找的目标则搜索结束返回该元素的位置。如果目标值小于中间元素则在左半区间low 到 mid-1继续搜索更新 high mid - 1。如果目标值大于中间元素则在右半区间mid1 到 high继续搜索更新 low mid 1。 重复步骤2和3直到找到目标值或搜索区间为空即 low high此时表明目标值不在列表中。 二分搜索法的时间复杂度为 O(log n)其中 n 是列表中元素的数量。这意味着对于大规模数据集合二分搜索远比顺序搜索时间复杂度为 O(n)高效。然而为了应用二分搜索列表必须事先排序且通常适用于静态数据或不频繁插入删除操作的数据结构。 可以看出二分搜索法顾名思义就是不断来缩小我们的搜索区间来查找特定元素的一种高效算法而在使用二分搜索法时关键的地方就在于如何确定我们的区间边界。
1.2解法思路
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size()-1;while(left right){int madile left(right - left) / 2;if(nums[madile] target){right madile - 1;}if(nums[madile] target){left madile 1;}if(nums[madile] target){return madile;}}return -1;}
};开始我们可以给定一个左闭右闭的区间是左区间left 0右区间right nums.size -1此时判断边界时就需要考虑左区间和右区间的关系时小于等于还是小于
开始我们的思路时给定一个左闭右闭的区间也就是说左区间的值可以等于右区间所以在第一个边界判断时我们的左区间是可以等于右区间的。
当我们对目标值进行判断后我们的左右区间又该如何判断呢
第一种情况当我们所要查找的目标值小于区间中值时我们需要考虑的是此时的右区间right是等于madile还是等于madile-1回到判断条件中nums[madile] target这表示我们区间的中值已经大于我们的目标值了所以我们下一次的判断时已经不需要考虑madile所以此时的右区间应该是madile-1。
同样的道理当区间中值小于目标值时我们要更新左区间的值此时左区间的值为madile1。
1.3扩展
题目原文
给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
**注意**不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4
输出2示例 2
输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。这道题使用二分法的思路如下
要使用二分法找到非负整数 x 的算术平方根的整数部分你可以遵循以下步骤 初始化两个指针left 和 right。因为我们要找的是非负整数的平方根所以 left 初始化为 0而 right 初始化为 x。如果 x 是 0则直接返回 0。 进入一个循环只要 left 小于等于 right就继续循环。 在每次循环中计算 mid它是 left 和 right 的中间值向下取整然后检查 mid * mid 是否等于 x。如果是那么 mid 就是我们要找的平方根直接返回它。 如果 mid * mid 大于 x说明我们超出了目标平方根因此需要将 right 更新为 mid - 1。 如果 mid * mid 小于 x说明目标平方根还在 mid 的右侧包括 mid因此需要将 left 更新为 mid 1。 循环结束后left 会指向我们找到的整数平方根因为循环条件是 left right当循环停止时实际上 left 可能已经超过了正确的答案但由于我们是向下取整寻找平方根最终正确的整数平方根是 left - 1除非 x 是完全平方数。
题解
class Solution {
public:int mySqrt(int x) {if (x 0 || x 1) {return x;}int left 0, right x;while (left right) {int mid left (right - left) / 2;long long square static_castlong long(mid) * mid;if (square x) {return mid;} else if (square x) {left mid 1;} else {right mid - 1;}}return left - 1;}
};
