Binary Search Exercise

In this assignment you are given a program which reads integers from a file into a dynamically allocated array and then prompts the user to enter integers to search for. When the user enters an integer, the program performs a linear search to determine whether or not the integer is in the array, and prints “Yes” or “No” depending on whether or not the integer is in the array.

You are to alter this program so that it checks to see if the integers from the file are in sorted order, and if so performs recursive binary search instead of a linear search.

Existing Functionality

Before making changes, try running the existing program to see its behavior. You will need to create at least one text file containing integers for testing. Let’s say you create a file named test.txt with the following contents:

1 4 5 8 9

Running make will produce the executable search. A run of the program would look like this:

$ ./search test.txt
Enter integers to search for. To quit press ctrl+d or enter a non-integer string
1
Yes
2
No
3
No
4
Yes

Note that if you enter more than one integer on one line, scanf() will scan them one by one. So you could check for 1, 2, 3, and 4 on one line, and the program would print out the results of each search on separate lines:

$ ./search test.txt
Enter integers to search for. To quit press ctrl+d or enter a non-integer string
1 2 3 4
Yes
No
No
Yes

Project Structure

main() calls the function load_array() to read the integers from the file, and then uses a loop to repeatedly call linear_search() for each number that the user enters. The load_array() and linear_search() functions are implemented in search.c and their prototypes are located in search.h.

You are to change the code so that it performs a binary search instead of a linear search. For a binary search to work the integers in the file must be in sorted order. So you will add two functions to the search module, one to check that an array is sorted and another to perform a recursive binary search. These functions will be tested individually, so their prototypes must match the following:

/*
 * Determines whether or not an array is sorted in ascending order.
 *
 *   Parameters:
 *     array - the array under consideration
 *     size - the number of elements in the array
 *
 *   Return value:
 *      true if the array is sorted in ascending order, false if it is not
 */
bool is_sorted(int *array, size_t size);

/*
 * Performs a recursive binary search to determine whether or not an integer
 * is in an array. The array must be sorted.
 *
 *   Parameters:
 *     target - the integer to search for
 *     array - the array to search in
 *     size - the number of elements in the array
 *
 *   Return value:
 *     true if the target is in the array, false if it is not
 */
bool binary_search(int target, int *array, size_t size);

These prototypes have already been placed in search.h for you. Implement the two functions in search.c. In main(), call is_sorted() on the array before the loop that performs the searches, and print an error message and return 3 if the array is not sorted. Replace the call to linear_search() in the loop with a call to binary_search().

Recursive binary search works by picking an element in the middle of a portion of an array and comparing it to the target. If the middle element is the target, then the search is over and we can return true. If the middle element is greater than the target, we return the result of repeating the binary search on the portion of the array to the left of the middle element. If the middle element is less than the target, we return the result of repeating the binary search on the portion of the array to the right of the middle element. For the base case, return false immediately if the size of the array is 0.

Let’s call the index of the middle element middle. We can find middle by computing size / 2. Note that for an array with an odd size this will round down, which is what we want since the first index is 0 (for an array of size 3, the middle index is 1). For an array of even size there is no true middle. This division will choose the middle to be the leftmost element in the right half of the array (for an array of size 4, the middle index is 2).

For the recursive call using the portion of the array to the left of the middle, you can pass the same array pointer since the left portion of the array starts at the same location as the original array, but you need to pass the new smaller size.

For the the recursive call using the portion of the array to the right of the middle, the pointer that you pass needs to be a pointer to the element just to the right of the middle element. To get this pointer you can simply add middle + 1 to array. You will need to calculate the new size as well.

See the notes from class for illustrations of this.

Submission

Push your submission to gitkeeper. Your code will be automatically tested. For full credit your code must adhere to all the requirements in the instructions and use proper style.