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

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=\lfloor \frac{n}{2}\rfloor$的地方：
        1. 如果运气够好，这个位置的元素恰好就是 X，即 $arr[p]=X$，那直接返回 $p$ 即可；
        2. 如果运气不够好，这个位置的元素 $arr[p]>X$，说明元素 X 在 p 的左边，因此将数组查找范围减半（把下标大于等于 p 的元素都忽略），只关注 arr[p - 1] 及之前的元素即可；
        3. 如果这个位置的元素 $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 函数等，以及 开区间 等写法，其实原理就一个：二分，答案在哪边，就往哪边走。