Ezvor

8. Binary Search

EasyBinary Search Verified judge

Given a sorted (ascending) array of distinct integers nums and a target, return the index of target if it exists, otherwise return -1. You must write an O(log n) algorithm.

Example 1

Input

6
-1 0 3 5 9 12
9

Output

4

Example 2

Input

6
-1 0 3 5 9 12
2

Output

-1

Input format

Input: line 1 = n, line 2 = n sorted integers, line 3 = target.
Output: the index, or -1.

Constraints

  • 1 ≤ n ≤ 10^4
  • Array is sorted ascending with distinct values

Expected output

4