j**l
发帖数: 2911 | 1 给出了递归和非递归的版本。
考虑如下的test case
int array[4] = {3, 4, 5, 6};
int lower = 1;
int upper = 2;
int target = 2;
对递归的版本，将返回LIMITS_REVERSED。
对非递归的版本，将返回ARRAY_UNORDERED
实际上两个版本对这个case都应该返回NOT_IN_ARRAY
PIE书把range == 0 && array[lower] != target 作为检测到NOT_IN_ARRAY并且立即返
回。而在编程珠玑中，没有LIMITS_REVERSED的错误类型，在range == 0 && array[
lower] != target的情况下并不立即返回，而是继续更改lower或upper,直到lower >
upper, 并将lower > upper作为NOT_IN_ARRAY的条件。
const int NOT_IN_ARRAY = -1;
const int ARRAY_UNORDERED = -2;
const int LIMITS_REVERSED = -3;
i | j**l
发帖数: 2911 | 2 二分查找有不少变体，包括环状有序数组，找重复元素中的第一个或者最后一个，一定
要多练习。
下面是一个Google真题
1 1 1 2 2 2 3 3 3 3
找第一个出现的数字的位置，
如果要找2，返回数组下标3
找最后一个出现的数字的位置，
如果要找2，返回数组下标5
这个在Programming Pearls里头有提到，关于找第一个或者最后一个出现的数字的位置
原理有两个
1. 当找到其中一个匹配的时候不返回而是继续找，但原来代码的high = mid - 1 (或
low = mid + 1)一定要改成high = mid (或low = mid)，否则有可能会漏过要找的元素
2. 搜索的range包含不多于两个元素的时候就要停止，否则根据1, 有可能会在还剩两
个元素或者一个元素的时候进入死循环 | l****q
发帖数: 177 | |
|
