- Exercise 1 Implementing Recursive Binary Search Assume That You Have A List Of Names All Lower Case Which Are Alphabe 1 (51.21 KiB) Viewed 20 times
- Exercise 1 Implementing Recursive Binary Search Assume That You Have A List Of Names All Lower Case Which Are Alphabe 2 (35.03 KiB) Viewed 20 times
Exercise 1: Implementing Recursive Binary Search Assume that you have a list of names (all lower case) which are alphabetically ordered ordered_namese ['ayla', 'ben', 'can', 'david', 'eliz', 'fatma', 'gene', 'huseyin', 'kemal', 'en', 'liam', 'matt', 'zach' You should implement a recursive function that checks whether a given input name is in this given inputtist or not. If the name is in the list, your implementation should return True, otherwise it should return False To have a good and fast running recursive implementation, you can use the Binary Search approach. In the Binary Search approach, you first compute the mid-point index, and then you check whether or not the mid-point of the list is smaller (or greater). There are many online resources available on this toplo and you are welcome to search on Google "Binary Search to get more info on Binary Search In our problem, we can use Binary Search approach to check if the element in the list located at the mid-point is alphabetically smaller than the given input name. If the mid-point element is smaller, then we continue the search in the upper half of the list (mid+1 to end). If the mid-point element is greater, we continue the search in the lower half (begining to mid-1). If the mid-point element is equal to name, we are done and return True. Regardless of which half of the list has been chosen, we repeat the previous step for it and keep repeating until we end up with an empty list. In that case we return False since we don't have the name in the list. ordered_names = ['ayla', 'ben", 'can', 'david', 'eliz', 'fatma', 'gene', 'huseyin', 'Kemal', 'ken', 'liam', 'matt', 'zach '1
L'ayta True Exercise 2: Implementing the same problem with iterative methods Implement the same (above-given) problem without using recursion. You will need to use the same input (Use iterative methods.) 11: Exercise 3: Comparison of both approaches In this part, we will study which one of those two implementations that you have already implemented runs faster. First compute the time required to run your implementation in Exercise 1 you can use the same code that you used in Exercise 1 here), and then compute the time required to run your implementation in Exercise 2. Compare the times required time values at the end in your code and print the last running algorithm's name to the screen In [l: