Question

Binary search can be implemented as a recursive algorithm. Complete the recursive function binarysearch() with the following specifications: parameters: a target integer, a vector of integers, lower and upper bounds within which the recursive call will search. Return value: the index within the vector where the target is located, -1 if the target is not found. The algorithm begins by choosing an index midway between the lower and upper bounds. If target == (index), return index. If lower == upper, return -1 to indicate not found. Otherwise, call the function recursively on half the vector parameter: if (index)

a. Complete the recursive function as specified.
b. Implement binary search iteratively.
c. Use linear search instead of binary search.
d. Ignore the given specifications.

Answer 1

Binary search is an algorithm used to find a specific element in a sorted array. It can be implemented as a recursive function that repeatedly divides the search space in half. The iterative implementation uses a loop, while linear search checks each element one by one.

Step-by-step explanation:

Binary search is an algorithm used to find a specific element in a sorted array or list. It works by repeatedly dividing the search space in half until the target element is found or the search space is empty.

The recursive implementation of binary search involves defining a function that takes in a target integer, a vector of integers, and the lower and upper bounds within which to search. The algorithm starts by choosing an index that is midway between the lower and upper bounds. If the target element is found at that index, the function returns the index. If the lower and upper bounds are equal, it means the target element is not in the array and the function returns -1. Otherwise, the function calls itself recursively on either the lower or upper half of the array, depending on the comparison result between the target and the element at the chosen index.

To implement binary search iteratively, you would use a loop instead of recursion. The loop continuously updates the lower and upper bounds and the chosen index until the target element is found or the search space is empty.

Using linear search instead of binary search means checking each element in the array one by one until the target element is found or all elements have been checked. This approach is less efficient than binary search, especially for large arrays.