P007 二分查找

题目描述

给定一个升序排列的整数数组 a 和目标值 target，找到 target 在数组中的第一个下标（从 0 开始），如果不存在则输出 -1。

时间复杂度要求：O(\log n)。

输入格式

第一行两个整数 n, target（1 \le n \le 10^6）。
第二行 n 个升序排列的整数 ai。

输出格式

一个整数，表示 target 的第一个下标；不存在则输出 -1。

样例

输入:
6 4
1 2 3 4 4 5

输出: 3