Binary Search on a Sorted Array

You are given a sorted array of integers and a target integer. Your task is to implement the binary search algorithm that determines whether the target exists in the array.

The binary search algorithm works in \(O(\log n)\) time by repeatedly dividing the search interval in half. Initially, the search interval is the entire array. 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. Repeatedly check until the value is found or the interval is empty.

You need to write a complete program that reads from stdin and outputs the result to stdout.

inputFormat

The input consists of three parts:

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

outputFormat

Output a single line with the word "true" if the target exists in the array; otherwise, output "false".

5
1 2 3 4 5
3

true