4.8 查找数组：线性查找与折半查找

程序员经常要处理数组中存放的大量数据，可能需要确定数组是否包含符合某关键值(key value)的值。寻找数组中某个元素的过程称为查找(searching)。本节介绍两个查找方法：简单的线性查找（liner search）方法和更复杂的折半查找（binary search）方法。练习4.33和练习4.34要求用递归法实现线性查找与折半查找。

图4.19 的线性查找比较数组中每个元素与查找键（search key）。由于数组没有特定的顺序，很可能第一个就找到，也可能要到最后一个才找到。因此，平均起来，程序要比较数组中一半的元素才能找到查找键值。要确定哪个值不在数组中，则程序要比较查找键与数组中每一个元素。

1 // Fig. 4.19: fig04_19.cpp
2 // Linear search of an array
3 #include <iostream.h>
4
5 int linearSearch( const int [], int, int );
6
7 int main()
8 {
9 const int arraySize = 100;
10 int a[ arraySize ], searchKey, element;
11
12 for(int x = 0; X < arraySize; x++ ) // create some data
13 a[ x ] = 2 * x;
14
15 cout << "Enter integer search key:" << endl;
16 cin >> searchKey;
17 element = linearSearch( a, searchKey, arraySize );
18
19 if ( element != -1 )
20 cout << "Found value in element " << element << endl;
21 else
22 cout << "Value not found" << endl;
23
24 return 0;
25 }
26
27 int linearsearch( const int arraay[], int key, int sizeofArray )
28 {
29 for (int n = 0; n < sizeofArray; n++ )
30 if( arraay[ n ] == key )
31 return n;
32
33 return -1;
34 }

输出结果：

Enter integer search key:
36
found value in element 18

Enter integer search key:
37
Value not found

图4.19 数组的线性查找

线性查找方法适用于小数组或未排序数组。但是，对于大数组，线性查找是低效的。如果是排序数组，则可以用高速折半查找。

折半查找算法在每次比较之后排除所查找数组的一半元素。这个算法找到数组的中间位置，将其与查找键比较。如果相等，则已找到查找键，返回该元素的数组下标。否则将问题简化为查找—半数组。如果查找键小于数组中间元素，则查找数组的前半部分，否则查找数组的后半部分。如果查找键不是指定子数组(原始数组的一部分)中的中间元素，则对原数组的四分之—重复这个算法。查找一直继续，直到查找键等于指定子数组中的中间元素或子数组只剩一个元素且不等于查找键(表示找不到这个查找键)为止。

在最糟糕的情况下，查找1024个元素的数组只要用折半查找进行十次比较。重复将1024除2(因为折半查找算法在每次比较之后排除所查找效组的一半元素)得到值512、256、128、64、32、16、8、4、1和1。数值1024(210)除2十次之后即变成1。除以1就是折半查找算法的一次比较。

1048576(220)个元素的数组最多只要20次比较就可以取得查找键。十亿个元素的数组最多只要30次比较就可以取得查找键。这比线性查找的性能大有提高，后者平均要求比较数组元素个数一半的次数。对于十亿个元素的数组，这是5亿次比较与30次比较的差别。折半查找所需的最大比较次数可以通过大于数组元素个数的第一个2的次幂的指数确定。

性能提示4.6

折半查找所带来的巨大的性能提高是有代价的，比起一次查找一个项日，排序数组的成本要高得多。如乘数组需要多次高速查找．则排序数组的开销是值得的。

图4.20显示了函数 binarySearch 的迭代版本。函数取4个参数，一个整数数组b、一个整数 searehKey、low 数组下标和 high 数组下标。如果查找键不符合于数组的中间元素，则调整 low 数组下标和 high 数组下标，以便查找更小的子数组。如果查找键小于中间元素，则 high 数组的下标设置为 middle-1，继续查找 low 到 middle-1 的元素。如果查找健大于中间元素，则 low 数组的下标设置为 middle+1，继续查找 middle+1 到 high 的元素。程序使用15个元素的数组。大于数组元素个数的第一个2的次幂是 16(24)，因此寻找查找健最多只要四次比较。函数 printHeader 输出数组下标，函数 printRow 输出折半查找过程中的每个子数组。每个子数组的中间元素标上星号(*)，表示用这个元素与查找键比较。

1 // Fig. 4.20: fig0420.cpp
2 // Binary search of an array
3 #include <iostream.h>
4 #include <iomanip.h>
5
6 int binarySeareh( int [], int, int, int, int );
7 void printHeader( iht ,
8 void printRow( int [], int, int, int, int );
9
10 int main()
11 {
12 const iht arraySize = 15;
13 int a[ arraySize ], key, result;
14
15 for ( int i = 0; i < arraySize; i++ )
16 a[ i ]= 2 * i; // place some data in array
17
18 cout << "Enter a number between 0 and 28: ";
19 cin >> key;
2O
21 printHeader( arraySize );
22 result = binarySearsh( a, key, 0, arraySize - 1, arraySize );
23
24 if ( result != -1 )
25 cout << '\n' << key << "found in array element"
26 << result << endl;
27 else
28 cout << '\n' << key << "not found" << endl;
29
30 return 0;
31 }
32
33 //
34 int binarysearch( int b[ ], int searchKey, int low, int high,
35 int size )
36 {
37 int middle;
38
39 while ( low <= high ) {
40 middle = ( low + high ) / 2;
41
42 printRow( b, low, middle, high, size );
43
44 if ( searchKey == b[ middle ] ) // match
45 return middle;
46 else if ( searchKey < b[ middle ] )
47 high = middle - 1; // search low end of array
48 else
49 low = middle + 1; // search high end of array
50 }
51
52 return -1; // searchKey not found
54
55 // Print a header for the output
56 void printHeader( int size )
57 {
58 cout << "\nSubscripts:\n";
59 for (int i = 0; i < size; i++ )
60 cout << setw( 3 ) << i << ' ';
61
62 cout << '\n';
63
64 for ( i = 1; i <= 4 * size; i++ )
65 cout << '-';
66
67 cout << endl;
68 }
69
70 // Print one row of output showing the current
71 // part of the array being processed.
72 void printRow( int b[ ], int low, int mid, int high, int size )
73 {
74 for ( int i = 0; i < size; i++ )
75 if ( i < low || i > high )
76 cout << " ";
77 else if ( i == mid ) // mark middle value
78 cout << setw( 3 ) << b[ i ] << '*';
79 else
80 cout << setw( 3 ) << b[ i ] << ' ';
81
82 cout << endl;
83 }

输出结果：

Enter a number between 0 and 28:25

Subscripts:
O 1 2 3 4 5 6 7 8 9 10 11 12 13 14
------------------------------------------------------------------------------
O 2 4 6 8 10 12 14* 16 18 20 22 24 26 29
                 16 18 20 22* 24 26 28
                          24 26* 28
                          24*
25 not found

Enter a number between 0 and 28: 8

Subscripts：
O 1 2 3 4 5 6 7 8 9 lO ll 12 13 14
------------------------------------------------------------------------------
O 2 4 6 8 lO 12 14* 16 18 20 22 24 26 28
O 2 4 6* 8 10 12
      8 lO* 12
      8*
8 found in array element 4

Enter a number between O and 28: 6

Subscrlpts：
O l 2 3 4 5 6 7 8 9 10 11 12 13 14
------------------------------------------------------------------------------
O 2 4 6 8 10 12 14* 16 18 20 22 24 26 28
O 2 4 6* 8 10 12
6 found ln array element 3

图4.20 排序数组的折半查找过程