Binary Search in a Sorted Array

You are given a sorted array of integers and a target value. Your task is to implement the binary search algorithm to find the index of the target in the array. If the target exists in the array, output its index; otherwise, output -1.

The binary search algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Continue until the value is found or the interval is empty.

Note: The binary search algorithm has a time complexity of \(O(\log n)\).

inputFormat

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

outputFormat

Output a single integer representing the index of \(target\) in the array if it exists. Otherwise, output -1.

6
-1 0 3 5 9 12
9

4