Classwork 16: Searching
Objectives
Practice working with arrays as function parameters.
The Assignment
Your assignment is to extend the Bubble Sort program shown in class: bubble4.c. Your program will allow the user to specify the input file, sort the data read into the array and then allow the user to search the array.
Step 1: Copying
You will need 3 files bubble4.c, cw16data1.txt and cw16data2.txt. You can copy these in the GL file system using the Unix cp command:
cp /afs/umbc.edu/users/c/h/chang/pub/cs104/bubble4.c . cp /afs/umbc.edu/users/c/h/chang/pub/cs104/cw16data1.txt . cp /afs/umbc.edu/users/c/h/chang/pub/cs104/cw16data2.txt .
Change the name of bubble4.c to search.c:
mv bubble4.c search.c
Step 2: Input File
Recall from Classwork 3 that strings can be processed by printf() and scanf() using the %s placeholder. (See for example scanf1.c.) Notice that in the C programming language, strings are just arrays of char.
Modify your copy of search.c so it prompts the user for a file name. You will need to declare an array of characters to store the file name. For now, assume that file names will not exceed 64 characters. Pass that string to the ReadArray() function.
Compile and test your program with the two test files before proceeding to the next step. Running your program should look something like this:
PT[109]% ./a.out Filename: cw16data1.txt Read in 25 numbers into array A[] from file cw16data1.txt. Before sorting: 294 199 205 80 295 6 236 80 290 169 33 281 110 198 160 191 57 234 100 177 274 198 209 219 220 After sorting: 6 33 57 80 80 100 110 160 169 177 191 198 198 199 205 209 219 220 234 236 274 281 290 294 295 PT[110]%
Step 3: Linear Search
One reason to sort an array is that it makes searching in the array easier. Imagine looking for a word in a dictionary where the words are not alphabetized. It would be much harder!
In this step, you will implement a function that looks for a number in the sorted array A[]. In computer science, this number being searched for is called the key. If the function finds the key, then it returns the index of A[] where the key appears. Otherwise it should return −1.
The prototype of your function should be:
int LinearSearch(int key, int A[], int size) ;
Inside the LinearSearch() function, you must write a for loop or a while loop that steps through the array A[] to look for the key. To take advantage of the fact that A[] is already sorted, you should stop searching when you encounter a number in A[] that is larger than the key, since the remaining numbers will also be larger than the key. (Assuming you step through the array from smallest to largest.)
Modify the main() function so it prompts the user for a key to search and uses LinearSearch() to find the key. The main program should also report the return value from LinearSearch(). Test your program with both cw16data1.txt and cw16data2.txt. Test your program with several keys, including cases where the key is in A[] and when the key is not in A[]. Running your program should look something like:
PT[109]% ./a.out Filename: cw16data1.txt Read in 25 numbers into array A[] from file cw16data1.txt. Before sorting: 294 199 205 80 295 6 236 80 290 169 33 281 110 198 160 191 57 234 100 177 274 198 209 219 220 After sorting: 6 33 57 80 80 100 110 160 169 177 191 198 198 199 205 209 219 220 234 236 274 281 290 294 295 Enter key: 203 Key 203 not found in array A[]. PT[110]% ./a.out Filename: cw16data1.txt Read in 25 numbers into array A[] from file cw16data1.txt. Before sorting: 294 199 205 80 295 6 236 80 290 169 33 281 110 198 160 191 57 234 100 177 274 198 209 219 220 After sorting: 6 33 57 80 80 100 110 160 169 177 191 198 198 199 205 209 219 220 234 236 274 281 290 294 295 Enter key: 205 Key 205 found in position 14 of array A[]. PT[111]%
Step 3: Binary Search (time permitting)
A linear search does not take full advantage of a sorted array. Binary search is much faster. In binary search, we look at the number in the middle of the array A[]. If it is smaller than the key, then we search for the key in the second half of A[]. Otherwise, we look in the first half of A[]. Recall that this was the strategy used in Homework 6 when you wrote a program to play "I'm thinking of a number".
As in that program, here you will have two variables lowEnd and highEnd. You will maintain the invariant that if the key is in the array A[], then it must be between A[lowEnd] and A[highEnd] (inclusive).
Let newGuess be halfway between lowEnd and highEnd:
newGuess = (lowEnd + highEnd) / 2 ;
Then there are three possibilities:
- The key might be equal to A[newGuess].
- The key might be in A[lowEnd] through A[newGuess - 1] (inclusive).
- The key might be in A[newGuess+1] through A[highEnd] (inclusive).
In the first case, you have found the key. In the second case, you should let newGuess - 1 be the new highEnd. In the third case, you should let newGuess + 1 be the new lowEnd.
Unlike the situation in "I'm thinking of a number", here the possibility exists for highEnd to be less than lowEnd because the key might not be in the array A[]. For example, if lowEnd is 2 and highEnd is 3, then newGuess is 2 (because integer division truncates). If the key is less than A[2], then highEnd becomes 1. This means the key is not in the array and your function should return −1.
Add a binary search function to your program. The function prototype should be the same as for LinearSearch:
int BinarySearch(int key, int A[], int size) ;
Modify your main() function to call BinarySearch() instead of LinearSearch(). (Don't delete LinearSearch(). Keep both in your file.) Test your program with both cw16data1.txt and cw16data2.txt.
Submit
When you are done testing your program, use the script command to record yourself compiling the program and running on both cw16data1.txt and cw16data2.txt. Test your program with several keys, including cases where the key is in A[] and when the key is not in A[]. Then, submit as usual:
submit cs104_chang cw16 search.c typescript