Binary Search in Sorted Array

You are given a sorted array of n integers and a target integer. Your task is to implement the binary search algorithm to find the target's index in the array. If the target is not present, return -1.

The binary search algorithm works in a logarithmic time complexity of \(O(\log n)\) by repeatedly dividing the search interval in half. Initially, the search interval covers the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

inputFormat

The input is read from stdin and consists of three lines:

1. The first line contains an integer \(n\) denoting the number of elements in the array.
2. The second line contains \(n\) space-separated integers sorted in non-decreasing order.
3. The third line contains a single integer representing the target value to search for.

outputFormat

Output a single integer to stdout representing the index of the target in the array if found, or -1 if the target is not in the array.

## sample

7
1 2 4 6 7 9 11
7

4

</p>