一、二分查找法简介

二分查找法又称为折半查找法，这种查找方法需要待查的查找表满足两个条件：

首先，查找表必须使用顺序存储结构；

其次，查找表必须按关键字大小有序排列。

二、时间复杂度

二分查找法就是每次少一半，多少次之后变为 1 ，如果总个数是 16

即 2^x = 16,求 x

即 log2(16)

如果总数为 n

即 log2(n)

即 二分查找法的时间复杂度。

三、实现代码

1、非递归的二分查找

public static int binSearch(int[] array, int findValue) {
// 如果数组为空，直接返回-1，即查找失败
if (array == null) { return -1;  }
// 起始位置
int start = 0;
// 结束位置
int end = array.length - 1;
while (start <= end) {
   // 中间位置
   int middle = (start + end) / 2;
   // 中值
   int middleValue = array[middle];
   if (findValue == middleValue) {
       // 等于中值直接返回
       return middle;
   } else if (findValue < middleValue) {
       // 小于中值时在中值前面找
       end = middle - 1;
   } else {
      // 大于中值在中值后面找
      start = middle + 1;
   }
}
// 返回-1，即查找失败
return -1;
}

2、递归的二分查找

/**
*  二分查找
* @param srcArray 有序数组
* @param start 数组开始位置
* @param end   数组结束位置
* @param key   查找的key
* @return
*/
public static int binSearch (int array[], int start, int end, int key) {
int mid = (end + start) / 2;
      if (start > end) {
         return -1;
      }
      if (array[mid] == key) {
         return mid;
      } else if (key > array[mid]) {
         return binSearch(array, mid + 1, end, key);
      } else {
         return binSearch(array, start, mid - 1, key);
      }
}