CSE030-Lab 5 Binary Search Solved

(Exercise 1) Create – fileIO.cpp 
In this part of the lab you will write a program that does the following operations:

•       Reads words from a file (words_in.txt), with one word per line.

•       Creates an array, using dynamic memory allocation, large enough to contain those words (one word per array element).

•       Output the words (array elements) to another file (words_out.txt).

Before storing the words from a file in an array, you will need to first find out how many lines there are in the file: one way to do it is to check with a counter when you reach the end of the file, by using the function eof().  eof() returns true (1) if the end of file is reached, otherwise a false (0) is returned.   

Once you have found out how many lines there are in the file, you can create a dynamically allocated array of strings, which is as large as the number of words contained in the file (as per the counter you have implemented).  You can review the syntax to declare arrays with dynamic memory allocation (pointer / new) in the lecture slides or at cplusplus.com.

Finally, you will write each word (array element) into the output file, one word per line.

 

Note:

•       You do not need to declare an array with a pre-defined constant size nor ask the user to input the number of elements.

•       Make sure that you create an input file with only one word per line.

 

(Exercise 2) Create – checkArray.cpp
In this part of the lab, you will create a function checkArraySort that checks if an array of strings (which was previously defined and initialized) is already sorted, and it is either increasing or decreasing.   The function that you create is declared as follows:  

•       Input arguments:

o   A string array A (remember that array is a pointer in this case, so use the * sign)

o   an integer variable array_size for the number of elements in array A (the counter value from previous exercise)  

•       Return in integer value:

o   -1 if the array is sorted in descending order o 0 if the array is not sorted o 1 if the array  is sorted in ascending order

You can modify the main program that you developed in fileIO.cpp to call checkArraySort, and to print out one of the following statements:

•       If -1                  “The array is sorted in descending order!”

•       If 0                   “The array is not sorted!”

•       If 1                   “The array is sorted in ascending order!”

You can use the same words_in.txt to test your program.

Note:  In order to check the sorting of strings / words, you can use the comparison operators (<, <=, ==, >, >=) the same way you would compare numbers.

 

(Exercise 3) Create – searchArray1.cpp 
In this part of the lab, you will create a recursive function that searches for a key in an array with a binary search algorithm.  Revisit lecture# 4 for the concept of the binary search algorithm.  All you need to do is to repeat splitting an array by half and compare the key to the value of the middle element.

In main program:

•       Input an array from a file.

•       Call function (checkArraySort) to check if the array is sorted.  So far, you can use the code you created from the previous exercises.

•       Exit program if the array is not sorted, or continue if it is. Therefore, you can use the code that you built so far (exercise 2), and continue to the next steps if the array is sorted.

•       Prompt the user to input search key (k).

•       Call function (binarySearchR) to search for the key recursively.

•       Output your search result:

o “Found key k at index i!” if the key was found. o “The key k was not found in the array!” if the key was not found.

Your binarySearchR function will return an integer value i as the index of the array A where the key is found (or -1 in key is not found), and it will take the following arguments:

•       a string array A (again, it is a pointer)

•       the number of elements in the array

•       the key to search for (a string)

Before writing your binarySearchR function, think about the algorithm and write it in pseudocode using a piece of paper or a text editor.  You need to turn in the pseudocode to receive full credit.

 

(Exercise 4) Create – searchArray2.cpp 
In this part of the lab, you will create a search function (binarySearchL) that is similar to exercise 3 with the following change:

•       You will implement the binary search algorithm using a loop instead of a recursive function.

This time all you need to do is to call a search function you create with the following arguments:

•       a string array A (again, it is a pointer)

•       the number of elements in the array

•       the key to search for (a string)

Return:

•       -1 if the key was not found

•       index of the (first) element where you found the key.

Your program should behave the same way as searchArray1.cpp in the previous exercise; therefore, you may reuse the main function in searchArray1.cpp

Hint:  You may use the same logic to find the beginning, end, and mid-point of an array you used for the recursive binary search.  You will use a loop to compare the values of the array to the key until the calculated mid-point is the last element.