Binary Search on a Sorted Array

You are given a sorted array of n integers in non-decreasing order and a target value. Your task is to implement the binary search algorithm to determine whether the target exists in the array.

The binary search algorithm works by comparing the target with the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target is found or the remaining half is empty.

The time complexity of binary search is \(O(\log n)\). Ensure your implementation handles edge cases such as an empty array or arrays with a single element.

inputFormat

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

1. The first line contains a single integer n indicating the number of elements in the array.
2. The second line contains n space-separated integers representing the sorted array (if n is 0, this line may be empty).
3. The third line contains a single integer representing the target value to search for.

outputFormat

Output a single line to stdout containing either True if the target is found in the array, or False otherwise.

6
-1 0 3 5 9 12
9

True