1.二分查找又称折半查找

2.优点：比较次数少;查找速度快;平均性能好

3.缺点：待查表为有序数组（若为无序数组，分成两份查找无意义，排序本身也耗费时间）;插入删除困难（增删需要移动大量的节点）

4.思想：

在一个有序数组中，取数组的中间值与要查找的数进行比较；

若要查找的数等于中间值，查找成功；

若要查找的数大于中间值，则在右半区间继续取中间值与要查找的数进行比较；

若要查找的数小于中间值，则在左半区间继续取中间值与要查找的数进行比较；

直至最后要查找的数与中间值相同，则说明找到该值，查找成功；若查找区域无此数，查找失败。

在有序数组中查找某个数，找到返回数的下标，存在多个返回任意一个即可，没有返回-1。

查找某个数在有序数组中首次出现的位置，

对arr[mid] == key 的情况做特殊处理，检查前一个位置元素是否是重复元素；

查找某个数在有序数组中最后一次出现的位置，

对arr[mid] == key 的情况做特殊处