Recursive Linear Search and Binary Search
CS 103 Lab - Rehearse to Recurse For extra credit you can attempt to write the selection sort algorithm recursively by using a loop to find the maximum and put it at the last location but then using recursion to process the list of size n-1 each time 4 Procedure 4.1 [7 pt.] Binary Search Go to Lab8: Binary Search in Vocareunm You will see the following files binsearch.cpp sorted data.in un sorted-data.in // skeleton code you will modify / sorted list of integers to search // unsorted list of integers tsearc Now make the following alterations: 1. Examine the list of integers in sorted_data.in and unsorted_data.in which your c ode will need to search through for a value provided by the user (via cin Open binsearch.cpp and examine and understand the skeleton code. As a point of interest understand the code that counts how many integers are in the file before reading them in Implement a recursive binary search algorithm in the binsearch() function 2. 3. You may NOT use any explicit while/for loops...you must use recursion Remember the start index is inclusive but the end index is exclusive (i.e. 1 beyond the actual last index to be searched) . 4. Compile your code (check for any warnings that may be generated) compile binsearch.cpp -o binsearch 5. Run your code and test it with some values that are and aren't present in the sorted_data.in file $.binsearch sorted data.in Check the results to ensure it matched your expectation (make sure you have an expectation of what should be output) 6. Demo your code to your TA/CP 4.2 [3pts.+2 EC for recursive implementation] Selection Go to Lab8: Binary Search in Vocareunm Recall that binary search only works on sorted data. So if we are given unsorted data we would first have to sort it befoewe can call binary search Uncomment line 48 which calls the sort() function (the skeleton code is shown below...uncomment that call to sort) 7. 8. // Uncomment the line below for part 2 / sort (data, count) Last Revised: 8/19/2018 CS 103 Lab - Rehearse to Recurse Implement a selection sort algorithm in the sort() function that sorts the data in the array passed as an argument. It should sort the data in place (i.e. DON'T declare another blank array and fill that array in with sorted data) 9. Selection sort is easily implemented with two nested loops (for or while) 10. For 2 extra credit points implement a recursive implementation of selection sort. [Note: Sorting a list of size N can be achieved by placing the maximum value in the list at the last location (and moving the value there to some other location) and then sorting a list of size N-1 that doesn't include that last item.] 11. You are not allowed to change the prototype (add or remove parameters or return values) of the sort() function. You may however define a new helper function with alternate parameters/return values to help implement the recursion 12. Compile your code (check for any warnings that may be generated). Compile binsearch.cpp -o binsearch Run your code and test it with some values that are and aren't present in 13. unsoreted_data.in $ ./binsearch unsorted data.in Check the results to ensure it matched your expectation 14. Demo your code to your TA/CP Last Revised: 8/19/2018 CS 103 Lab - Rehearse to Recurse For extra credit you can attempt to write the selection sort algorithm recursively by using a loop to find the maximum and put it at the last location but then using recursion to process the list of size n-1 each time 4 Procedure 4.1 [7 pt.] Binary Search Go to Lab8: Binary Search in Vocareunm You will see the following files binsearch.cpp sorted data.in un sorted-data.in // skeleton code you will modify / sorted list of integers to search // unsorted list of integers tsearc Now make the following alterations: 1. Examine the list of integers in sorted_data.in and unsorted_data.in which your c ode will need to search through for a value provided by the user (via cin Open binsearch.cpp and examine and understand the skeleton code. As a point of interest understand the code that counts how many integers are in the file before reading them in Implement a recursive binary search algorithm in the binsearch() function 2. 3. You may NOT use any explicit while/for loops...you must use recursion Remember the start index is inclusive but the end index is exclusive (i.e. 1 beyond the actual last index to be searched) . 4. Compile your code (check for any warnings that may be generated) compile binsearch.cpp -o binsearch 5. Run your code and test it with some values that are and aren't present in the sorted_data.in file $.binsearch sorted data.in Check the results to ensure it matched your expectation (make sure you have an expectation of what should be output) 6. Demo your code to your TA/CP 4.2 [3pts.+2 EC for recursive implementation] Selection Go to Lab8: Binary Search in Vocareunm Recall that binary search only works on sorted data. So if we are given unsorted data we would first have to sort it befoewe can call binary search Uncomment line 48 which calls the sort() function (the skeleton code is shown below...uncomment that call to sort) 7. 8. // Uncomment the line below for part 2 / sort (data, count) Last Revised: 8/19/2018 CS 103 Lab - Rehearse to Recurse Implement a selection sort algorithm in the sort() function that sorts the data in the array passed as an argument. It should sort the data in place (i.e. DON'T declare another blank array and fill that array in with sorted data) 9. Selection sort is easily implemented with two nested loops (for or while) 10. For 2 extra credit points implement a recursive implementation of selection sort. [Note: Sorting a list of size N can be achieved by placing the maximum value in the list at the last location (and moving the value there to some other location) and then sorting a list of size N-1 that doesn't include that last item.] 11. You are not allowed to change the prototype (add or remove parameters or return values) of the sort() function. You may however define a new helper function with alternate parameters/return values to help implement the recursion 12. Compile your code (check for any warnings that may be generated). Compile binsearch.cpp -o binsearch Run your code and test it with some values that are and aren't present in 13. unsoreted_data.in $ ./binsearch unsorted data.in Check the results to ensure it matched your expectation 14. Demo your code to your TA/CP Last Revised: 8/19/2018
