2.4.2 折半查找（2）
4. binarySearch如何给出查找结果？如果binarySearch成功地从数组中找到target，那么将返回target对应的数组元素的索引。索引一定不是负值，因此如果没有在数组中找到target，那么binarySearch会返回负值。
下面的C++函数binarySearch实现了上述思想。为了在后面对该函数进行箱式跟踪，将对binarySearch的两个递归调用分别标记为X和Y。
- /** Searches the array anArray[first] through anArray[last]
- for a given value by using a binary search.
- @pre 0 <= first, last <= SIZE - 1, where SIZE is the
- maximum size of the array, and anArray[first] <=
- anArray[first + 1] <= ... <= anArray[last].
- @post anArray is unchanged and either anArray[index] contains
- the given value or index == -1.
- @param anArray The array to search.
- @param first The low index to start searching from.
- @param last The high index to stop searching at.
- @param target The search key.
- @return Either index, such that anArray[index] == target, or -1.
- */
- int binarySearch(const int anArray[], int first, int last, int target)
- {
- int index;
- if (first > last)
- index = -1; // target not in original array
- else
- {
- // If target is in anArray,
- // anArray[first] <= target <= anArray[last]
- int mid = first + (last - first) / 2;
- if (target == anArray[mid])
- index = mid; // target found at anArray[mid]
- else if (target < anArray[mid])
- // Point X
- index = binarySearch(anArray, first, mid - 1, target);
- else
- // Point Y
- index = binarySearch(anArray, mid + 1, last, target);
- } // end if
- return index;
- } // end binarySearch
注意，如果数组中包含了target，那么必然存在于first和last界定的数组段中。也就是说，下面的内容是成立的：
- anArray[first] target anArray[last]
图2-10显示了binarySearch查找的箱式跟踪，在此这个函数查找包含1、5、9、12、15、21、29和31的数组。注意在图中用X和Y标记了binarySearch的两次递归调用。本章结尾的练习题16要求完成这个函数的其他箱式跟踪。
提示：当开发递归解决方案的时候，必须确保较小问题的解决方案确实可以提供原始问题的解决方案。例如，当每个较小的数组都已经被排序，并且被查找的值在第一个值和最后一个值之间时，binarySearch才起作用。
此外还需要考虑一个C++特有的实现问题。数组不会按值传送给函数，因此不存在数组的副本。C++的这种特征对诸如binarySearch这样的递归函数特别有用。如果数组anArray很大，就有可能需要多次递归调用binarySearch。如果每次调用都复制anArray，将造成内存和时间的大量浪费。此外由于不复制anArray，因此函数可以修改数组中的元素，除非像binarySearch那样把anArray指定为const。
注释：由于数组参数总是按引用传递，因此如果没有将数组指定为const，则函数可以修改数组
对于包含数组参数的递归函数的箱式跟踪，需要考虑另一个因素。因为数组anArray既不是值参数也不是局部变量，所以它并不是函数局部环境的一部分，各个箱内不应包含数组anArray的全部内容。因此，anArray在箱外表示，如图2-11所示，对anArray的所有引用都会影响这个表示。
注释：在箱式跟踪时，将引用参数放在箱外表示
提示：注意计算中点mid的C++语句为：
- int mid = first + (last - first)/2;
而不是伪代码中建议的：
- int mid = (first + last)/2;
如果打算查找一个元素数量为230(大约10亿)的数组，first与last的和可能超过最大的int值230-1。因此，计算first+last时将溢出从而得到一个负整数，进而使得mid成为负值。如果将这个值为负的mid用作数组的索引，将导致数组越界并得到不正确的结果。表达式first+(last-first)/2在代数上等同于(first+last)/2，但是避免了这个问题。
