Lab07, CISC105 Summer 2005

Directions

• Write a program for each of the following problems. If you wish, you may start each program using a previous program as a base and then modifying it, BUT you will learn more if you code each one from scratch. Be sure to save every separate program. All programs must be properly commented and indented (see Assignment Standards on the class website).
• Some programs below are associated with a question. Answer the question using comments in your code.
• During your scripting of the programs, you will compile and run each one. If a program does not compile, don't try to run it (because a.out will not have been created).
• Name each program lab07.n.c, where n is the number in the list below. For example, the name of the file for the first will be lab07.1.c

Practicing UNIX

% cc -o mysearch lab07.1.c
% ls
lab07.1.c     mysearch

Programs

1. (30) Linear Search for Integers Create an integer array of 10 elements. Use a loop to fill it with the numbers 0-9.

   Now search the array using a linear search. Traverse the array looking for an element input by the user, and when you find it print the location and the element in an appropriate message. If the element is not found, print an appropriate message.

   To ease testing, add a loop to allow the user to request values to search for repeatedly. Don't restrict the user's input. Let your search function determine if the input is "valid".

2. (45) Binary Search for Integers Now make a second program with the same framework, but add a function that does binary search. The prototype will be int binarySearch(int data[], int key, int low, int high);

   For the function definition, declare a variable "mid" that will be near the center of the part of the array between low and high; set it equal to the midpoint between low and high. Run your function to be certain it works so far, and print mid. Try it with various lows and highs.

   Key is the element we are searching for.

   We must now handle four cases in our code:

   1. If key is less than the element at data[mid], you will recursively call our function on the same array, the same key, and what two indices for low and high? Draw a picture to be sure you have it right.
   2. If key is greater than the element at mid, you will recursively call our function on the same array, the same key, and what two indices for low and high? Draw a picture to be sure you have it right.
   3. If key is equal to mid, what would be an informative number for the function to return?
   4. If the key is not in the array, how would you know that is the case and how should you handle that case?

   After you write and debug the function, change your program to use an array of size 100 using all even numbers.

   Finally, add an array of size 1000. Put a print statement inside your search function so you can see how many times it is called. What elements take the longest to find?

3. (30) Linear Search for Strings Based on program lab07.1.c, create a similar program to search an array of strings. Create an array of 10 strings. Fill it with the words in the file.

   Now search the array using a linear search. Traverse the array looking for an element input by the user, and when you find it print the location and the element in an appropriate message.

4. (45) Binary Search for Strings Based on programs lab07.2.c and lab07.3.c, make appropriate changes to create a program that uses binary search to find strings.
5. (40) Binary Search for Employees Create a struct for employees that contains the employee's id, first name, and last name. Initialize an array of 10 employees, in id order. Allow a user to search for employees by id.

You should have a total of 5 programs named lab07.1.c to lab07.5.c. Make a single script file (see lab00 for the instructions) where you cat, compile, and run each one in its final form (if it didn't compile, don't run it in the script - mark the place in the printed script file with a marker so it stands out).

Note: Cat, compile, and run each program in order! Do not cat all programs, then compile, etc.

Execute your program multiple times to show that you tested the program well.

More Practicing UNIX

Submission

Grading