二分法查找是一道基本的算法题，近期本人面试，遇到好多面试官让手写 二分法 ，今天就来总结下：

二分查找 是一种查询效率非常高的查找算法，又称折半查找。二分查找可以用递归的方法较简单的实现，另外不用递归也能实现（本人面试遇到让不用递归的方式实现）。

二分查找图示说明

二查法查找示例图

代码实现

二分查找两种实现代码

测试类

时间复杂度

时间复杂度来说，递归与非递归的方式都一样，在最坏的情况下的时间复杂度为O(log2 N)，即x次之后找到，n/2^x=1;最好情况下为O（1），即第一次就找到。

空间复杂度

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

非递归方式：由于辅助空间是常数级别的，所以空间复杂度是O(1);

递归方式： 递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的，空间复杂度：O(log2N )