二分法 Bi-partition

定义

二分法是一种算法，其输入是一个有序的元素列表。

如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null 。

基本思想

1. 当数据量很大适宜采用该方法。
2. 采用二分法查找时，数据需是排好序的
3. 假设数据是按升序排序的，对于给定值 key，从序列的中间位置 mid 开始比较:
4. 如果当前位置 arr[mid] 值等于 key，则查找成功；
5. 若 key 小于当前位置值 arr[mid]，则在数列的前半段中查找 arr[low,mid-1]；
6. 若 key 大于当前位置值 arr[mid]，则在数列的后半段中继续查找 arr[mid+1,high] 直到找到为止。

时间复杂度：