Algorithms in a Nutshell

Binary Search | 115

Searching

We ran 100 trials of 524,288 searches for an item stored in a collection in memory

of sizen(ranging in size from 4,096 to 524,288) with probabilityp(sampled at 1.0,

0.5, and 0.0) of finding each item. After removing the best and worst performers

for each trial, Table 5-2 shows the average performance for the remaining 98

trials.

These trials were designed to ensure that for thep=1.0 case all elements in the

collection are being searched for with equal probability; if this were not the case,

the results could be skewed. For both SEQUENTIAL SEARCHand BINARY

SEARCH, the input is an array of sorted integers in the range [0,n). To produce

524,288 search items known to be in the collection (p=1.0), we cycle through the

n numbers 524,288/n times.

Table 5-3 shows the times for performing 524,288 searches on a collection stored

on a local disk. The searched-for item either always exists in the collection (e.g.,

p=1.0) or it never does (e.g., we search for –1 in the collection [0,n)). The data is

simply a file of ascending integers, where each integer is packed into four bytes.

The dominance of disk access is clear since the results in Table 5-3 are nearly 200

times slower than those in Table 5-2. Asndoubles in size, note how the perfor-

mance of the search increases by a fixed amount, a clear indication that the

performance of BINARYSEARCH is O(logn).

Table 5-2. In-memory execution of 524,288 searches using Binary Search compared to

Sequential Search (in seconds)

n Sequential Search time Binary Search time

p = 1.0 p = 0.5 p = 0.0 p = 1.0 p = 0.5 p = 0.0

4,096 3.8643 5.5672 7.2143 0.0809 0.0773 0.0704

8,192 7.2842 10.7343 14.1308 0.0861 0.0842 0.0755

16,384 14.0036 20.9443 27.7101 0.0928 0.0902 0.0814

32,768 27.8042 40.7164 54.3972 0.0977 0.1065 0.1067

65,536 54.8484 81.1192 107.8211 0.1206 0.1155 0.1015

131,072 107.6957 161.6651 215.1825 0.1246 0.1251 0.1127

262,144 * * * 0.1373 0.1346 0.1232

524,288 * * * 0.1479 0.1475 0.133

Table 5-3. Secondary-storage Binary Search performance for 524,288 searches (in seconds)

n p = 1.0 p =0.0

4,096 2.8403 2.8025

8,192 3.4829 3.4942

16,384 4.1842 4.0046

32,768 4.9028 4.7532

65,536 5.5598 5.449

131,072 6.4186 6.1808

262,144 7.1226 6.9484

524,288 7.8316 7.4513

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use