Searching and Sorting
This chapter explores two very practical problems: searching and sorting. We consider Linear Search and (two versions of) Binary Search. Binary trees are used to describe the search process. Binary search is much, much better but requires sorted input. We
- PDF / 1,430,890 Bytes
- 52 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 250 Views
Searching and Sorting
After all that theory, this chapter returns to very practical problems, searching and sorting. Imagine maintaining the records of a bank, drugstore, or college. Most often, files of accounts are kept and updated periodically. Each account is identified by a “key”: a bank account number or customer’s name or a student’s ID number. When a record is to be displayed and/or changed, the first step is to find it in the collection of records. Let’s restrict our attention to the problem of determining whether or not a certain number occurs in a certain list of keys. // On the way, we’ll admire a forest of Binary Trees.
4.1
Searching
The search problem is Given an array A[1], A[2], A[3], . . . , A[n] and a target value T, find an index j where T ¼ A[ j] or determine that no such index exists because T is not in the array A.
4.1.1
Searching an Arbitrary List
Names in telephone books are not kept in arbitrary order and probably neither are student records. But consider the problem of finding your car in a parking lot when you’ve forgotten where you left it. If parking spaces are selected at random by drivers as they arrive, how would you find your car? // A solution algorithm sometimes applied by tipsy students is random walk: // // (a) Pick a direction N, S, E, or W at random and take a step in that direction; // if you bump into the edge of the parking lot, take a step back; but // if you bump into a car, try your car key and // if the key works, stop the search. (Here is a key a key?) T. Jenkyns and B. Stephenson, Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, Undergraduate Topics in Computer Science, DOI 10.1007/978-1-4471-4069-6_4, # Springer-Verlag London 2013
131
132
4
Searching and Sorting
// (b) Go back to (a) and pick again. // // Would you believe that this algorithm can be proved to be effective // (in a certain “probabilistic” sense)? A more practical algorithm would be as follows: Look at the parked cars one at a time in some order, say, from the beginning of the first row to the end of the first row, then back along the second row to its beginning, and so on until the last car in the last row is checked (if necessary). Stop searching when you’ve found your car or when you’ve checked all the positions in the lot (perhaps your car is not there because it’s been stolen, seized by the bank, impounded by the police, borrowed by your sister, or left at home). The algorithm of comparing the target value T to the value in each position in turn is known as a sequential or a Linear Search. Returning to the case of numerical keys, we have Algorithm 4.1.1: Linear Search Begin j 0; Repeat j jþ1 Until ((A[j] ¼ T) Or (j ¼ n)); If (A[j] ¼ T) Then Output(“T is A[”, j, “]”) Else Output(“T is not in A”) End; End. This algorithm is clearly correct – it will surely find the target if it is present and will surely terminate with a correct report if the target is not present. // It finds the first occurrence of T if T occurs in the array more than once. The cost of a s
Data Loading...
