二分查找介绍

二分查找（Binary Search）是一种高效的查找算法，用于在有序数组中查找特定元素的位置。

以在升序序列中查找目标元素为例：

1、初始状态下，将整个序列作为搜索区域（假设为 [B, E]）；

2、找到搜索区域内的中间元素（假设所在位置为 M），和目标元素进行比对。如果相等，则搜索成功；如果中间元素大于目标元素，表明目标元素位于中间元素的左侧，将 [B, M-1] 作为新的搜素区域；反之，若中间元素小于目标元素，表明目标元素位于中间元素的右侧，将 [M+1, E] 作为新的搜素区域；

3、重复执行第二步，直至找到目标元素。如果搜索区域无法再缩小，且区域内不包含任何元素，表明整个序列中没有目标元素，查找失败。

本题主要让大家学习二分查找，不要求测试全过，没AC不要紧的。

题目描述

找出数组按升序排序后目标元素所在的位置(即数组下标)。若不存在目标元素，输出 -1。

输入格式

第一行输入一个 N 表示元素的个数；

第二行输入 N 个数据存到数组 a 里面;、

第三行输入目标元素 target 。

输出格式

输出目标元素的位置 ；若不存在，输出 -1 。

输入输出示例

示例1：

输入

5
1 9 0 1 2
3

输出

-1

示例2：

输入

4
2 1 1 2
2

输出

2

数据限制

0 =< N <= 1e6