题目内容

给定一个包含 $n$ 个元素的升序整数数组 $nums$ 和一个目标值 $target$。

请在数组 $nums$ 中查找目标值 $target$。

如果 $target$ 存在于数组中，输出它在数组中的下标；如果不存在，则输出 $-1$。

数组下标从 $0$ 开始。

要求算法的时间复杂度为 $O(\log n)$。

输入描述

第一行输入两个整数 $n$ 和 $target$，分别表示数组 $nums$ 的长度和需要查找的目标值。

第二行输入 $n$ 个整数 $nums_i$，表示升序数组 $nums$ 中的元素，相邻整数之间用空格分隔。

约束

$1 \le n \le 10000$

$-9999 \le nums_i \le 9999$

数组 $nums$ 中的所有元素互不相同。

数组 $nums$ 按严格升序排列。

要求算法的时间复杂度为 $O(\log n)$。

输出描述

如果数组 $nums$ 中存在目标值 $target$，输出 $target$ 在数组中的下标。

如果数组中不存在 $target$，输出 $-1$。

样例1

输入

6 9
-1 0 3 5 9 12

输出

4

说明

目标值 $9$ 存在于数组 $nums$ 中，其下标为 $4$，因此输出 $4$。

样例2

输入

6 2
-1 0 3 5 9 12

输出

-1

说明

目标值 $2$ 不存在于数组 $nums$ 中，因此输出 $-1$。