Binary Search in Sorted Array

In this problem, you are given a sorted array of integers and a target integer. Your task is to implement the binary search algorithm to determine the index of the target in the array.

If the target exists, output its index (0-indexed); otherwise, output -1. The binary search algorithm works in O(\(\log n\)) time, where \(n\) is the number of elements in the array.

Note: When there are multiple occurrences of the target, returning the index of any one occurrence is acceptable; however, the input guarantees that all elements are unique.

inputFormat

The input is read from standard input (stdin) and contains three parts:

1. An integer \(n\) representing the number of elements in the array.
2. A line with \(n\) space-separated integers representing the sorted array.
3. An integer representing the target value to search for.

outputFormat

Output a single integer to standard output (stdout): the index of the target in the array if found; otherwise, output -1.

5
1 2 3 4 5
3

2