Binary Search: Iterative and Recursive Approaches

This problem requires you to implement a binary search algorithm using both iterative and recursive methods. Given a sorted array and a target value, your task is to determine the index of the target in the array. If the target is not present, output -1.

In the iterative approach, you repeatedly narrow down the search range. In the recursive approach, you call the function recursively with updated indices until the target is found or the range is exhausted.

The middle index is computed as \(\text{mid} = \text{left} + \lfloor (\text{right} - \text{left})/2 \rfloor\), which helps prevent potential overflow issues.

inputFormat

The input consists of 4 lines:

• The first line is a string indicating the search method. It can be either iterative or recursive.
• The second line contains an integer n representing the number of elements in the array.
• The third line contains n space-separated integers which form a sorted array in non-decreasing order.
• The fourth line contains an integer representing the target value.

outputFormat

Output a single integer: the index of the target in the array if it exists; otherwise, output -1.

iterative
9
1 2 3 4 5 6 7 8 9
5

4