二分查找学习

折半查找的思想十分简单，其效率也很高；但是要将其运用到实际程序中却并不容易，需要考虑很多细节上的问题。

在数组中查找

设 arr 为一个数组， target 为目标值。假设 arr 已经是升序排序过的并且下文中默认这个条件。取 arr 的长度为\(L\)。

查找值

假定需要在 arr 中查找是否存在等于 target 的元素，如果查找到了则返回对应元素的下标；否则返回\(-1\)。

对于这种情况，返回结果的范围是\(\{-1\} \bigcup \{0,1,\dots ,L-1\}\)，因此取初始区间\([l, r]\)为\([0,L-1]\)，若找到 target 直接返回 mid ，否则一直查找，最后返回\(-1\)即可。值得注意还有结束条件，由于查找的有效结果是一个值，因此要保证区间\([0,L-1]\)中没有遗漏的值，那么必须保证没有找到的条件下，退出时的区间\([l,r]\)满足\(l > r\)，可以得出循环条件为\(l \leqslant r\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int findVal(vector<int> arr, int target) {
	int l = 0, r = arr.size() - 1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (arr[mid] == target) {
			return mid;
		}
		else if (arr[mid] > target) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return -1;
}

查找界

假定要查找 arr 中 target 的上确界，并且要求如果所有元素均大于等于 target 则返回\(0\)，如果所有元素均小于等于 target 则返回\(L\)。

对于这种情况，返回结果的范围是\(\{0,1,\dots ,L-1\} \bigcup \{L\} = \{0,1,\dots ,L-1,L\}\)，因此取初始区间\([l, r]\)为\([0,L]\)，若 target \(\leqslant\) arr[mid] ，那么可能的结果区间为\([l,mid]\)，则更新\(r=mid\)；否则更新区间为\([mid+1,r]\)。由于最终退出循环时为一个区间\([l,r]\)，其中\(l \leqslant r\)，那么结束条件为\(l \leqslant r\)，可以得出循环条件为\(l<r\)，最终的返回值为\(l\)。

1
2
3
4
5
6
7
8
9
10
11
12
13

int findSupremum(vector<int> arr, int target) {
	int l = 0, r = arr.size();
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (arr[mid] >= target) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;//返回第一个元素的下标
}

查找下确界同理。

1
2
3
4
5
6
7
8
9
10
11
12
13

int findInfimum(vector<int> arr, int target) {
	int l = 0, r = arr.size();
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (arr[mid] <= target) {
			l = mid;
		}
		else {
			r = mid - 1;
		}
	}
	return r;//返回最后一个元素的下标
}

findSupremum() 函数实现了查找第一个大于等于 target 的数的功能，findInfimum() 实现了查找最后一个小于等于 target 的数的功能。通过修改循环中分支的条件可以更改查找的功能。