苏州企业网站建,wordpress原创培训主题,做网站找模板,离线 wordpress6-10 二分查找 1 题目原文2 思路解析2.1 基本二分查找算法2.2 常用二分模板2.2.1 第一个大于等于目标值的元素下标2.2.2 第一个大于目标值的元素下标2.2.3 最后一个小于等于目标值的元素下标2.2.3 最后一个小于目标值的元素下标2.2.4 小结 3 代码实现3.1 本题代码实现3.1.1 递归… 6-10 二分查找 1 题目原文2 思路解析2.1 基本二分查找算法2.2 常用二分模板2.2.1 第一个大于等于目标值的元素下标2.2.2 第一个大于目标值的元素下标2.2.3 最后一个小于等于目标值的元素下标2.2.3 最后一个小于目标值的元素下标2.2.4 小结 3 代码实现3.1 本题代码实现3.1.1 递归法3.1.2 迭代法 3.2 常用模板2.2.1 第一个大于等于目标值的元素下标2.2.2 第一个大于目标值的元素下标 4 总结 1 题目原文 题目链接6-10 二分查找 本题要求实现二分查找算法。
函数接口定义
Position BinarySearch( List L, ElementType X );其中 List 结构定义如下
typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};L 是用户传入的一个线性表其中 ElementType 元素可以通过 、、 进行比较并且题目保证传入的数据是递增有序的。函数 BinarySearch 要查找 X 在 Data 中的位置即数组下标注意元素从下标 1 开始存储。找到则返回下标否则返回一个特殊的失败标记 NotFound。
裁判测试程序样例
#include stdio.h
#include stdlib.h#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};List ReadInput(); /* 裁判实现细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );int main()
{List L;ElementType X;Position P;L ReadInput();scanf(%d, X);P BinarySearch( L, X );printf(%d\n, P);return 0;
}/* 你的代码将被嵌在这里 */输入样例1
5
12 31 55 89 101
31输出样例1
2输入样例2
3
26 78 233
31输出样例2
0代码长度限制 16 KB 时间限制 100 ms 内存限制 64 MB
2 思路解析 在本篇文章中除了解决题目以外还将简单地总结一下二分查找算法二分查找是一个灵活的算法即使有基本模板可以套用但是一般的二分查找题目都需要对基本模板进行修改这需要读者能深刻理解二分查找算法的原理原理并不难。而且基本模板的实现细节也因人而异选择自己喜欢的一个基本模板即可只需要记住一套基本模板然后随题意去修改这个基本模板即可。
2.1 基本二分查找算法 基本二分查找算法就是从一个升序数组 arr 中查找元素 X 是否存在注意数组中的数是不重复的。目的一般是返回元素 X 在数组中的下标如果不存在则返回一个约定的值常见的是 -1数组长度 n等。 我现在不知道这个数在哪里甚至连它在不在数组里面都不知道要怎么找呢那我就猜它在数组的正中间即下标为 p ⌊ n 2 ⌋ p\lfloor\frac{n}{2}\rfloor p⌊2n⌋的地方 1. 如果运气够好这个位置的元素恰好就是 X即 a r r [ p ] X arr[p]X arr[p]X那直接返回 p p p 即可 2. 如果运气不够好这个位置的元素 a r r [ p ] X arr[p]X arr[p]X说明元素 X 在 p 的左边因此将数组查找范围减半把下标大于等于 p 的元素都忽略只关注 arr[p - 1] 及之前的元素即可 3. 如果这个位置的元素 a r r [ p ] X arr[p]X arr[p]X说明元素 X 在 p 的右边同理将数组查找范围减半把下标小于等于 p 的元素都忽略只关注 arr[p 1] 及之后的元素即可。 经历一遍上面猜想的步骤可以看到问题又变得和原问题一样了在一个缩小了的数组里寻找元素 X。不难得出下面的递归思路伪代码
# arr: 升序数组
# X: 待查找元素
# start: 待查找数组的左边界闭区间
# end: 待查找数组的右边界闭区间
f(arr, X, start, end):if start end:# 这里返回 -1 表示没找到return -1# 猜想X在数组中间位置mid (start end) / 2if arr[mid] X:# 猜对了直接返回下标return midif arr[mid] X:# 没猜对X在mid的左边则朝左边寻找将右界变小return f(arr, X, start, mid - 1)# 没猜对X在mid的右边则朝右边寻找将左界变大return f(arr, X, mid 1, end)但是我们一般不喜欢递归解法除非只有递归解法不然的话都要看看能不能把递归转为迭代。上面的递归思路转为迭代还是很好办的并且符合人的一般思维如下
f(arr, X):l 0 # 待查找数组的左边界闭区间假设数组下标从0开始r arr.length - 1 # 待查找数组的右边界闭区间假设数组下标从0开始while l r:mid (l r) / 2if arr[mid] X:return midif arr[mid] X:r mid - 1;else:l mid 1;# 如果 X 存在则一定会在循环中找到并返回不会执行这一句如果执行了这句表示 X 不存在# 这里假设 X 不存在时返回 -1return -1上面就是基本二分查找算法的思路也是本题所考察的知识点。为什么要数组中的元素不重复呢这是因为这里只考虑元素 X 在不在数组中如果在则返回其下标如果有多个 X 的话那么应该返回哪个下标呢随便返回一个下标一般是不合理的。所以就干脆直接限制数组元素不重复。
2.2 常用二分模板 如果是为了解决本题那么上一小节就已经解决了。这一小节主要补充几个常用模板这些模板可用于任何非递减数组非递增数组同理。
2.2.1 第一个大于等于目标值的元素下标 有一个非递减数组 arr长度为 n查找 arr 中第一个大于等于 X 的元素下标下标从 0 开始。 首先考虑两个特殊情况 1. 如果 X 小于 arr 中的最小元素则应该返回 0 2. 如果 X 大于 arr 中的最大元素则应该返回 n。 然后开始查找不过和上面查找存不存在的思路有所区别 1. 最中间那个下标 mid 处的值小于 X说明答案在 mid 右边 2. 最中间那个下标 mid 处的值大于等于 X说明答案在 mid 左边。 由此可以得到上面问题的答案直到最后数组左边界即为答案。 模板见代码实现。
2.2.2 第一个大于目标值的元素下标 有一个非递减数组 arr长度为 n查找 arr 中第一个大于 X 的元素下标下标从 0 开始。 首先考虑两个特殊情况 1. 如果 X 小于 arr 中的最小元素则应该返回 0 2. 如果 X 大于 arr 中的最大元素则应该返回 n。 然后开始查找不过和上面查找存不存在的思路有所区别 1. 最中间那个下标 mid 处的值小于等于 X说明答案在 mid 右边 2. 最中间那个下标 mid 处的值大于 X说明答案在 mid 左边。 由此可以得到上面问题的答案直到最后数组左边界即为答案。 模板见代码实现。
2.2.3 最后一个小于等于目标值的元素下标 有一个非递减数组 arr长度为 n查找 arr 中最后一个小于等于 X 的元素下标下标从 0 开始。 易知最后一个小于等于目标值的元素下标 第一个大于目标值的元素下标 - 1
2.2.3 最后一个小于目标值的元素下标 有一个非递减数组 arr长度为 n查找 arr 中最后一个小于 X 的元素下标下标从 0 开始。 易知最后一个小于目标值的元素下标 第一个大于等于目标值的元素下标 - 1
2.2.4 小结 上面的四种情况只需要实现两种情况即可参照 C 的 lower_bound 和 upper_bound 函数。其余两种情况可以由另外两种情况转化而来。容易知道的是前两种情况返回值的取值范围是 [0,n]后两种的返回值取值返回为 [-1,n-1]在应用二分查找时需要注意这些边界情况并小心处理。
3 代码实现
3.1 本题代码实现
3.1.1 递归法
Position BinarySearchHelp(List L, ElementType X, Position l, Position r) {if (l r) return NotFound;Position mid l (r - l) / 2;if (L-Data[mid] X) {return mid;}if (L-Data[mid] X) {return BinarySearchHelp(L, X, l, mid - 1);}return BinarySearchHelp(L, X, mid 1, r);
}Position BinarySearch(List L, ElementType X) {return BinarySearchHelp(L, X, 1, L-Last);
}3.1.2 迭代法
Position BinarySearch(List L, ElementType X) {Position l 1, r L-Last, mid 0;while (l r) {mid l (r - l) / 2;if (L-Data[mid] X) {return mid;}if (L-Data[mid] X) {r mid - 1;} else {l mid 1;}}return NotFound;
}3.2 常用模板
2.2.1 第一个大于等于目标值的元素下标
int first_ge(int* arr, int n, int target) {int l 0, r n - 1, mid 0;while (l r) {mid l (r - l) / 2;if (arr[mid] target) {r mid - 1;} else {l mid 1;}}return l;
}2.2.2 第一个大于目标值的元素下标
int first_ge(int* arr, int n, int target) {int l 0, r n - 1, mid 0;while (l r) {mid l (r - l) / 2;if (arr[mid] target) {r mid - 1;} else {l mid 1;}}return l;
}4 总结 二分算法是一种思想就像基本原理一样原理很好懂但是实现方法千变万化喜好因人而异上面所记录的都是一种 闭区间 的写法即数组的左边界和右边界都是同时取得到的另外还有 左闭右开 写法比如 C 的 lower_bound 函数等以及 开区间 等写法其实原理就一个二分答案在哪边就往哪边走。
