Given an array of integers nums sorted in ascending order and an integer target, write a function to search for target in nums. If target exists, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: -1 0 3 5 9 12
Target: 9
Output: 4

Example 2:

Input: -1 0 3 5 9 12
Target: 2
Output: -1

Input format: First line: sorted space-separated array. Second line: target.

Output format: Index of target or -1.