Binary Search

This problem requires you to implement the binary search algorithm. You are given a sorted array \(A\) of distinct integers and a target integer \(X\). Your task is to find and output the index of \(X\) in \(A\). If \(X\) is not present in the array, output \(-1\). The binary search algorithm must run in \(O(\log n)\) time.

Input is provided from the standard input (stdin) and the result must be printed to the standard output (stdout).

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\) which is the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the sorted array \(A\). All integers are distinct.
• The third line contains an integer \(X\), the value to search in the array.

outputFormat

Print a single integer representing the index of \(X\) in the array \(A\) (0-indexed) if present; otherwise, print \(-1\).

6
1 3 5 7 9 11
7

3