【函数题】6-10二分查找

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) / 2 if arr[mid] == X: # 猜对了，直接返回下标 return mid if 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) / 2 if arr[mid] == X: return mid if arr[mid] > X: r = mid - 1; else: l = mid + 1; # 如果 X 存在，则一定会在循环中找到并返回，不会执行这一句，如果执行了这句，表示 X 不存在 # 这里假设 X 不存在时返回 -1 return -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 函数等，以及 开区间 等写法，其实原理就一个：二分，答案在哪边，就往哪边走。