题目描述

实现一个二分查找算法，输入一个升序排列的整数数组和一个目标值 $n$，返回 $n$ 在数组中的索引(下标从0开始)。如果 $n$ 不存在，返回-1。

格式

输入格式

输入有两行。第一行有若干个整数，一个升序排列的整数数组。

第二行有一个整数$n$。

输出格式

如果找到了 $n$，输出 $n$ 在数组中的索引，否则输出-1

样例

1 2 3 4 5
3

2

5 4 3 2 1
6

-1

数据范围与约定

输入的整数不超过int范围。

输入的个数不超过20个。