Binary Search in Sorted Array

Problem

Given a sorted array and a target, return the target's 0-based index, or -1 if absent. Must be O(log n).

Input

Line 1: n and target. Line 2: n ascending integers.

Output

Single integer — index or -1.

Constraints

1 ≤ n ≤ 10^6, -10^9 ≤ a[i], target ≤ 10^9

Sample input

5 7
1 3 5 7 9

Sample output

Explanation

7 sits at index 3 (0-based).

binary-searcharrays@Amazon@Microsoft

Visible test cases

in: 5 7
1 3 5 7 9

out: 3

in: 3 8
1 3 5

out: -1

Your solution — run it, use AI if stuck