唐河网站制作,沈阳好的互联网设计,永久免费自动建站系统,建设移动端网站题目一#xff1a;二分查找
二分查找 看到这道题之后#xff0c;很快就能想到暴力的解法#xff0c;把数组遍历一遍就能找到答案#xff0c;时间复杂度O(n)。
假设存在一批数字[1#xff0c;1#xff0c;3#xff0c;4#xff0c;5#xff0c;6#xff0c;7#x…题目一二分查找
二分查找 看到这道题之后很快就能想到暴力的解法把数组遍历一遍就能找到答案时间复杂度O(n)。
假设存在一批数字[11345678]目标数字是5。
我想在这一批数字中找到5这个数字该如何找当我随机挑选了一个数字4的时候4比5小4左边的数字都比4小所以可以在[5,8]区间找5这个数字继续随机挑选了7这个数字7比5大7后面的数字都比7大所以可以继续缩小区间把目标数字定位在[5,6]区间内。
二分查找算法
确定查找范围的起始点和终止点。计算中间点查看中间点的元素值与目标值的关系。如果中间点的元素值等于目标值查找成功。如果中间点的元素值大于目标值说明目标值可能在左半部分缩小查找范围至左半部分。如果中间点的元素值小于目标值说明目标值可能在右半部分缩小查找范围至右半部分。重复以上步骤直到找到目标值或确定目标值不在数组中。 当使用二分查找算法查找目标值时我们首先需要一个有序数组。让我们尝试查找目标值为7的索引假设有序数组为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。
初始状态 设定查找范围的起始点left和终止点right分别为数组的第一个和最后一个元素。此时left 0right 9。
第一轮查找 计算中间点的索引mid为 (left right) 1 4对应的值为 5。由于目标值 7 大于 5我们缩小查找范围到右半部分。更新 left mid 1即 left 5。
第二轮查找 新的中间点索引为 (left right) 1 7对应的值为 8。由于目标值 7 小于 8我们缩小查找范围到左半部分。更新 right mid - 1即 right 6。
第三轮查找 新的中间点索引为 (left right) 1 5对应的值为 6。由于目标值 7 大于 6我们缩小查找范围到右半部分。更新 left mid 1即 left 6。
第四轮查找 新的中间点索引为 (left right) 1 6对应的值为 7。因此我们找到了目标值 7并返回索引 6。
代码解析
class Solution {
public:int search(vectorint nums, int target) {int n nums.size();int l 0;int r n - 1;while (l r){int mid l r 1;if (nums[mid] target) r mid - 1;else if (nums[mid] target) l mid 1;else return mid;}return -1;}
};
题目二在排序数组中查找元素的第一个和最后一个位置
在排序数组中查找元素的第一个和最后一个位置 暴力解法从前往后扫描记录下来遇到目标数字的位置即可。
代码解析
依旧使用二分
class Solution {
public:vectorint searchRange(vectorint nums, int t) {int l 0, r nums.size() - 1;int n nums.size();int mid;int ansl -1;int ansr -1;if (n 0){return {ansl, ansr};}while (l r){ mid l (r - l 1);if (nums[mid] t) l mid 1;else r mid;}ansl l;l 0, r n - 1;while (l r){mid l (r - l 1 1);if (nums[mid] t) r mid - 1;else l mid;}ansr l;if (nums[ansl] ! t || nums[ansr] ! t) return {-1, -1};return {ansl, ansr};}
}; 模板
// 确定左端点
while (l r)
{ mid l (r - l 1);if (……) l mid 1;else r mid;
}// 确定右端点
while (l r)
{mid l (r - l 1 1);if (……) r mid - 1;else l mid;
}
