1. 二分查找的思想
二分查找是一种使用十分普遍的查找算法，其基本的思路也非常的简单，在一个有序的数据集合中，我们想要查找某个数据，直接取最中间的那个数据，将它和要找的数据进行比较，如果较大，则在更大的那个数值区间继续取中间值查找，反之亦然。
例如我们要在一个有序的集合里 [1，3，5，6，7，8，10]，查找 5 这个值，那么二分查找的过程就如下图所示，经过三次查找操作就能够找到。
2. 二分查找的实现
相信你已经能够理解二分查找的思路了，接下来看看它的代码实现。其实根据思路不难看出，二分查找有点分治的思想，所以代码可以用递归实现，也可以用循环实现。
二分查找的递归实现：
public class BinarySearch {
public static int binarySearchByRecursion(int[] data, int value) {
return binarySearchInternally(data, 0, data.length – 1, value);
}
private static int binarySearchInternally(int[] data, int low, int high, int value) {
while (low <= high){
// 计算中间值
int mid = low + ((high – low) >> 1);
if (data[mid] == value) return mid;
else if (data[mid] < value) return binarySearchInternally(data, mid + 1, high, value);
else return binarySearchInternally(data, low, mid – 1, value);
}
return -1;
}
}
二分查找循环实现：
public static int binarySearchByCircle(int[] data, int value) {
int low = 0;
int high = data.length – 1;
while (low <= high){
// 计算中间值
int mid = low + ((high – low) >> 1);
if (data[mid] == value) return mid;
else if (data[mid] < value) low = mid + 1;
else high = mid – 1;
}
return -1;
}
3. 二分查找的局限性
二分查找是一种很高效的算法，时间复杂度为 O(logn)，要是使用上的话，非常的方便。但是，二分查找对数据的要求也十分严苛。
首先，二分查找只适用于顺序表结构，说简单点，就是数组。因为可以利用数组下标访问的特性，快速取出数据进行比较。其他的数据结构例如链表，如果使用二分查找的话，不能进行下标访问，每次比较都必须遍历链表寻找中间节点，时间复杂度就很高了。
其次，二分查找针对的是有序数组，如果数据未排序，则必须进行排序才能够使用，前面说到了，排序的时间复杂度一般为 O(nlogn)。所以，二分查找较适用于一次排序，多次查找的数据。如果数据的插入和删除操作过于频繁，那么维护有序的成本就很高。
最后，二分查找适用于数据量较大的场景，假如我们要在几十或者几百个数据中进行查找，那直接遍历查找即可。面对大量的数据，二分查找方能体现其优势。