阿里巴巴网站怎么做全屏大图,网站建设合同图表版,网站建设无形资产的账务处理,小清新网站源码介绍:
二分查找算法#xff08;Binary Search#xff09;是一种在有序数组中查找目标元素的算法。 它的基本思想是通过将目标元素与数组的中间元素进行比较#xff0c;从而将搜索范围缩小一半。
如果目标元素等于中间元素#xff0c;则搜索结束#xff1b;如果目标元素小…介绍:
二分查找算法Binary Search是一种在有序数组中查找目标元素的算法。 它的基本思想是通过将目标元素与数组的中间元素进行比较从而将搜索范围缩小一半。
如果目标元素等于中间元素则搜索结束如果目标元素小于中间元素则继续在左半部分查找如果目标元素大于中间元素则在右半部分查找。
通过不断地将搜索范围缩小一半最终可以找到目标元素或确定目标元素不存在。
接下来通过例题介绍二分的不同写法
例题:
输入一个整数 n, 接下来一行输入 n 个整数(保证整数序列有序), 最后输入一个整数 m, 查找 m 在序列中的起始下标和结束下标
示例1:
输入: 5 1 2 2 4 5 2 输出: 1 2 解释:
2 在序列中的起始和结束位置是下标 1 和 2
代码讲解:
二分代码按照退出条件分为
while (l r)while (l r)
代码中的所有 l 和 r 都是序列的左右闭区间
代码中的所有 l r 1 和 l r 1 1 分别相当于 (l r) / 2 和 (l r 1) / 2。是按位右移, 整数向右位移一位相当于除2
代码中的所有 x, 都是目标值, 也就是要查找的值; 所有的 idx, 是答案, 也就是要查找数的起始下标或结束下标
先讲第一种: while (l r), 在l r时退出
// 查找起始下标
int l 0, r n - 1, idx 0;
while (l r)
{int mid l r 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] x) l mid 1; // 如果当前中间值比 x 小, 需要去序列的右区间, 因为mid位置的数比 x 小, 那么左边的区间(l, mid]的所有数都比 x 小else if (a[mid] x) r mid - 1; // 同上else if (a[mid] x) // 等于答案时{idx mid;r mid - 1; // 我们要找的时起始的下标, 虽然此时a[mid] x, 但是mid的左边可能还有等于x的值, 所以我们要继续往左区间去找}
}// 查找结束下标(代码中只有注释的地方和上面的代码不一样)
int l 0, r n - 1, idx 0;
while (l r)
{int mid l r 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] x) l mid 1; else if (a[mid] x) r mid - 1; else if (a[mid] x) {idx mid;l mid 1; // 我们要找的时结束的下标, 虽然此时a[mid] x, 但是mid的右边可能还有等于x的值, 所以我们要继续往右区间去找}
}观察上面代码我们可以把a[mid] x的情况跟其他两种情况合并
// 查找起始下标
int l 0, r n - 1, idx 0;
while (l r)
{int mid l r 1; // 一分为3, [l, mid), [mid, mid], (mid, r]if (a[mid] x) l mid 1; else if (a[mid] x){idx mid;r mid - 1; // 继续往左区间找}
}// 查找结束下标
int l 0, r n - 1, idx 0;
while (l r)
{int mid l r 1;if (a[mid] x){idx mid;l mid 1; // 继续往右区间找}else if (a[mid] x) r mid - 1;
}下面讲第二种: while (l r) 在l r时退出
大家可以发现这种写法不需要 idx 这个变量来记录最终查找的x的起始下标或结束下标了, 因为最后l就是对应的起始下标或结束下标。r等于l, 所以用r也行
查找起始下标
int l 0, r n - 1;
while (l r)
{int mid l r 1; // 区间分成了两个 [l, mid] 和 (mid, r]if (a[mid] x) l mid 1;// 当a[mid] x的时候, r一直往左, 所以当有多个相同的x的话, 会查找到第一个else if (a[mid] x) r mid; // 因为a[mid]可能 x, 因为mid也可能满足条件, 所以区间变成[l, mid]
}查找结束下标
int l 0, r n - 1, idx 0;
while (l r)
{ int mid l r 1 1; // 区间分成了两个 [l, mid) 和 [mid, r]if (a[mid] x) r mid - 1;// 当a[mid] x的时候, l一直往右, 所以当有多个相同的x的话, 会查找到最后一个else if (a[mid] x) l mid; // 因为a[mid]可能 x, 因为mid也可能满足条件, 所以区间变成[mid, r]
}接下来讲一下第二种查找结束下标的时候 为什么是 mid l r 1 1而不是 mid l r 1; c默认向0取整, 对于正整数你可以说是向下取整, 也就是 5 / 2 2, 当出现 l r - 1 的时候, 此时 mid (l r) / 2 向下取整后等于 r - 1 , 如果此时进入了a[mid] x的分支, 那么 l mid r - 1, 这时会发现 l 没有发生变化, 那么就会一直陷入死循环
先更到这里, 后面再补充
觉得写的不错的话, 点个赞吧
