BookHaven
All DSA problems
EasyBinary SearchGoogleMetaAmazon

Binary Search

Given a sorted array of integers nums (ascending) and a target, return the index of target if found, else print -1.

**Input**

First line: n target

Second line: n sorted integers

Examples

Example 1

Input:

6 9
-1 0 3 5 9 12

Output: 4

Example 2

Input:

6 2
-1 0 3 5 9 12

Output: -1

Constraints

  • 1 ≤ n ≤ 10^4
  • All values unique
  • Array is sorted ascending

Target: O(log n) time · O(1) space