Binary Search in a Sorted Book Catalog

You are given a sorted list of book titles from a library catalog. Your task is to perform a binary search to find the index of a target book title. If the book is found, output its index (0-based indexing); otherwise, output -1.

The binary search algorithm should operate in \(O(\log n)\) time, where \(n\) is the number of books. Note that the book titles are case-sensitive and sorted in ascending alphabetical order.

Implementation Details:

• You should not use any built-in search methods (e.g., language specific index functions or binary search libraries).
• Read input from stdin and write output to stdout.

Input Format (via stdin):

• The first line contains an integer \(n\) denoting the number of book titles.
• The next \(n\) lines each contain a book title (a non-empty string consisting of alphanumeric characters and spaces). These titles are provided in ascending alphabetical order.
• The last line contains the target book title you need to search for.

Output Format (via stdout):

Output a single integer representing the index of the target book. If the target is not found, output -1.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains an integer \(n\), the number of books.
• The next \(n\) lines each contain a book title (string), sorted in ascending order.
• The last line contains the target book title (string) to search for.

outputFormat

Output a single integer to stdout representing the index of the target book in the list. If the target book is not found, output -1.

## sample

5
A Tale of Two Cities
Animal Farm
Brave New World
The Great Gatsby
To Kill a Mockingbird
The Great Gatsby

3