2.4.2 折半查找（1）
查找是一种常见的任务，通常是在数组中查找某个特定项。下面讲述一些具有递归解决方案的查找问题。我们的目标是加深对递归的理解。
本章开始时曾给出高层的折半查找算法，在词典中查找单词。在此将完整地开发该算法，并阐述一些重要编程问题。
回顾前面词典问题的解决方案：
- search(aDictionary: Dictionary, word: string)
- if (aDictionary is one page in size)
- Scan the page for word
- else
- {
- Open aDictionary to a point near the middle
- Determine which half of aDictionary contains word
- if (word is in the first half of aDictionary)
- search(first half of aDictionary, word)
- else
- search(second half of aDictionary, word)
- }
注释：折半查找中，每一步解决一半问题
现在稍微调整一下问题--在整型数组anArray中查找指定值target。这个数组与词典一样必须经过排序，否则无法使用折半查找。在此假定：
- anArray[0] anArray[1] anArray[2] … anArray[size - 1]
其中size是数组的大小。对于这个数组问题，折半查找的伪代码如下所示：
- binarySearch(anArray: ArrayType, target: ValueType)
- if (anArray is of size 1)
- Determine if anArray's value is equal to target
- else
- {
- Find the midpoint of anArray
- Determine which half of anArray contains target
- if (target is in the first half of anArray)
- binarySearch(first half of anArray, target)
- else
- binarySearch(second half of anArray, target)
- }
从概念上讲，该算法非常合理，但在实现算法前，必须考虑几个细节：
1. 如何将anArray的一半传递给binarySearch的递归调用？可以在每次调用时传递整个数组，但是只让binarySearch查找anArray[first..last]，即从anArray[first]到anArray[last]的那部分。因此，还需要向binarySearch传递整数first和last。
- binarySearch(anArray, first, last, target)
按此约定，新的中点由下式确定：
- mid = (first + last) / 2
于是，binarySearch(first half of anArray, target)成为
- binarySearch(anArray, first, mid - 1, target)
而binarySearch(second half of anArray, target)成为
- binarySearch(anArray, mid + 1, last, target)
注释：原始数组的两半分别是anArray[first..mid-1]和anArray[first..mid+1]，二者都不包含anArray[mid]
2. 如何确定数组的哪一半包含target？if (target is in the first half of anArray)的一种可能实现为
- if (target < anArray[mid])
但是，此处没有检测target和anArray[mid]相等的情况。这个疏忽可能会让该算法丢失target。通过前面的等分算法将anArray分作两半后，这两半都不包含anArray[mid](此时，这两半无法组成原先完整的数组)。因此，必须确定anArray[mid]是不是正在查找的值，因为后面anArray[mid]将不再出现在剩下的一半数组中。等分标准与终止条件(基例)的交互很不容易理解，经常是错误的来源。我们需要重新考虑基例。
注释：判断anArray[mid]是否为查找的目标
3. 如何确定基例？如程序所示，只有在数组大小为1的情况下，binarySearch才终止，这是其唯一的基例。通过更改等分过程，可以将anArray[mid]保留在剩余的一半数组中，从而有可能正确实现折半查找，此时只有一个基例。然而，如果有下面两个不同的基例，程序将更加清晰易懂：
first>last。当原始数组中不存在target时，将到达此基例。
target==anArray[mid]。当target在原始数组中时，将到达该基例。
这些基例与前面提到的基例有所不同。从某种意义上来讲，算法根据到达的基例来确定问题的解。很多查找问题都是这样的。