Binary Search: Find the Target Index in a Sorted List

You are given a sorted list of integers and a target integer. Your task is to implement a binary search algorithm that finds the index of the target in the list. If the target does not exist in the list, output -1.

The binary search algorithm works by repeatedly dividing the search interval in half. Given a list \(A\) of size \(n\) and a target \(T\), the process is as follows:

1. Set \(left = 0\) and \(right = n - 1\).

2. While \(left \leq right\):

• Calculate \(mid = \lfloor (left + right)/2 \rfloor\).
• If \(A[mid] = T\), return \(mid\).
• If \(A[mid] < T\), search in the right half by setting \(left = mid + 1\).
• If \(A[mid] > T\), search in the left half by setting \(right = mid - 1\).

If the target is not found, return -1.

inputFormat

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

• The first line contains an integer \(n\) representing the number of elements in the list.
• The second line contains \(n\) space-separated integers in ascending order. If \(n = 0\), this line will be empty.
• The third line contains an integer representing the target value to search for.

outputFormat

Output a single integer to stdout representing the index of the target in the list using 0-based indexing. If the target is not found, output -1.

## sample

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

3