Binary Search in a Sorted Array

Given a sorted array of integers and a target integer, implement binary search to find the target's index in the array. If the target is not present, return -1. This problem is a classic example of applying the divide and conquer technique. The array is guaranteed to be sorted in non-decreasing order. Note that the index is 0-indexed. A formal representation of the sorted condition is given by \(A[i] \leq A[j]\) for all \(i < j\).

inputFormat

The input is given via standard input (stdin) and consists of three lines:

• The first line contains a single integer \(n\), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the sorted array.
• The third line contains a single integer \(target\), which is the value to search for.

outputFormat

Output a single integer to standard output (stdout): the index of the target in the array (0-indexed). If the target does not exist in the array, output -1.

6
-1 0 3 5 9 12
9

4