easyBinary Search

Binary Search

## Problem

Given a **sorted** array of distinct integers `nums` and a target value, return the index of `target` if it is in the array, or `-1` if it is not.

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

Examples

Input

nums = [-1,0,3,5,9,12], target = 9

Output

9 exists at index 4

Input

nums = [-1,0,3,5,9,12], target = 2

Output

-1

2 does not exist

Constraints

-10^4 <= nums[i], target <= 10^4 1 <= nums.length <= 10^4 nums is sorted in ascending order All integers in nums are unique

Python