Binary Search Template

Problem Description

Given a sorted strictly-increasing array (no duplicate elements), use binary search to find the position of the value $x$. If $x$ is not in the array, output -1.

Input Format

The first line contains an integer $n$, the number of array elements ($n \le 10^6$).

The second line contains $n$ numbers, the $n$ strictly-increasing array elements ($1\le$ element value $\le 10^8$).

The third line contains an integer $x$, the number to search for ($0\le x\le 10^8$).

Output Format

The (1-based) position of $x$ in the array, or $-1$.

Sample Input 1

10
1 3 5 7 9 11 13 15 17 19
3

Sample Output 1

2

Hint

Try to implement binary search both recursively and iteratively.