Binary Search in a Sorted Array

This problem requires you to implement a binary search algorithm to find a target value within a sorted array. The binary search algorithm works by repeatedly dividing the search interval in half and comparing the target value with the middle element.

If the target is equal to the middle element, the algorithm returns the index of the target (using 0-indexing). If the target is less than the middle element, the search continues on the left subarray; otherwise, it continues on the right subarray. If the target is not found, the algorithm returns -1.

The expected time complexity of the binary search is \(O(\log n)\), and it is assumed that the input array is sorted in non-decreasing order.

inputFormat

The input is received from standard input (stdin). 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 representing the target value to search for.

outputFormat

Output to standard output (stdout) a single integer: the 0-indexed position of the target in the array if it is found; otherwise, output \(-1\).

10
1 2 3 4 5 6 7 8 9 10
7

6