Modified Recursive Binary Search • Write C++ program hw7.cpp that meets the following requirements: – First, write a recursive binary search function with the following prototype: int binarySearch(int array[], int first, int last, int value); – Now suppose we have a sorted array like this: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; – Then the following statement int index = binarySearch(a, 0, SIZE-1, 22); – would return one of the indices that match the target value (22), and it could be index 4, 5, 6, or 7. – Now, your mission is to modify this recursive binary search function to always return the leftmost index when there are multiple indices that match the target value. Thus, in the above case, the function must return index 4. – If no match found, the function returns -1. – Write a main function that checks if your modified binary search function works as expected with at least 3 example arrays. – Note: your modified binary search function must ensure the time complexity of O(log2 n), where n is the array size, otherwise will incur huge point deduction (even if the program works). In layman’s terms, it means “no linear search allowed in any part of your program”. Example run: Input: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; Target: 22 Output: 4 Input: int a[SIZE] = { 3, 3, 3, 9, 12, 15, 20, 35, 51, 73 }; Target: 3 Output: 0 1 Input: int a[SIZE] = { 5, 9, 12, 22, 22, 22, 30, 35, 51, 63, 63 }; Target: 63 Output: 9 Input: int a[SIZE] = { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }; Target: 9 Output: 0 Input: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; Target: 25 Output: -1
Modified Recursive Binary Search • Write C++ program hw7.cpp that meets the following requirements: – First, write a recursive binary search function with the following prototype: int binarySearch(int array[], int first, int last, int value); – Now suppose we have a sorted array like this: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; – Then the following statement int index = binarySearch(a, 0, SIZE-1, 22); – would return one of the indices that match the target value (22), and it could be index 4, 5, 6, or 7. – Now, your mission is to modify this recursive binary search function to always return the leftmost index when there are multiple indices that match the target value. Thus, in the above case, the function must return index 4. – If no match found, the function returns -1. – Write a main function that checks if your modified binary search function works as expected with at least 3 example arrays. – Note: your modified binary search function must ensure the time complexity of O(log2 n), where n is the array size, otherwise will incur huge point deduction (even if the program works). In layman’s terms, it means “no linear search allowed in any part of your program”. Example run: Input: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; Target: 22 Output: 4 Input: int a[SIZE] = { 3, 3, 3, 9, 12, 15, 20, 35, 51, 73 }; Target: 3 Output: 0 1 Input: int a[SIZE] = { 5, 9, 12, 22, 22, 22, 30, 35, 51, 63, 63 }; Target: 63 Output: 9 Input: int a[SIZE] = { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }; Target: 9 Output: 0 Input: int a[SIZE] = { 3, 5, 7, 9, 22, 22, 22, 22, 30, 35, 51, 52, 73 }; Target: 25 Output: -1
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
