Tìm kiếm nhị phân (Binary Search)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $n$ số nguyên phân biệt $a_0,a_1,\ldots,a_{n-1}$ đã sắp xếp tăng dần và số nguyên target. Hãy tìm chỉ số của target. Nếu không tồn tại, in -1. Dãy đánh chỉ số từ $0$. Yêu cầu thời gian $O(\log n)$.

Input

Dòng đầu gồm $n$ và target. Dòng hai gồm $n$ số nguyên tăng dần.

Output

In chỉ số của target, hoặc -1 nếu không tìm thấy.

Subtask

• Subtask 1 — 20%: $1\le n\le100$.
• Subtask 2 — 30%: $1\le n\le1000$.
• Subtask 3 — 50%: $1\le n\le10^4$, $-10^4<a_i,\text{target}<10^4$.

Ví dụ

Input

6 9
-1 0 3 5 9 12

Output

4

Giải thích

9 nằm tại $a_4$, nên đáp án là $4$.