二分查找

算法特点

1. 二分查找算法是搜索算法中用得最多、最简单易用、效率较好的搜索算法。
2. 二分查找只能查找有序的数组。
3. 在使用二分查找算法前，必须对数组进行排序，而且在每次更改、插入、删除后都要进行排序以保证数组的有序状态。

算法步骤

1. 将要查找的值与数组的中间位元素进行比较，若小于中间位，则在前半部分区域查找，若大于中间位，则在后半部分区域查找，如果等于中间位，则直接返回。
2. 递归重复以上操作，知道范围缩到最小，如果还是没有找到匹配的元素，则说明元素并不在数组里。

复杂度

1. 平均时间复杂度为$O(logN)$