二分查找（Binary Search）算法，也称折半查找算法，类似分治思想。
二分查找针对一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间范围缩小至之前的一半，直至找到要查找的元素，或者区间范围被缩小为0。
复杂度分析
二分查找的时间复杂度为O(log n)，虽然二分查找的时间负责度为O(log n)，但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值，如O(1000)。
局限性分析
- 二分查找依赖数组结构
二分查找需要利用下标随机访问元素，使用链表等其他数据结构无法使用二分查找； - 二分查找针对有序数据
二分查找需要有序的数据，如果数据无序则首先需要排序，排序的时间复杂度最低是O(n log n)。所以如果针对一组静态数据，没有频繁插入、删除场景，可以进行一次排序、多次二分查找，将排序成本均摊。如果数据存在频繁插入、删除场景，则每次执行二分查找前都要先进行排序，成本很高。所以，二分查找最好用在插入、删除频率低，一次排序多次查找的场景中。 - 数据量太小不适合二分查找
数据量很小时顺序遍历即可。 - 数据量太大不适合二分查找
二分查找底层依赖数组结构，数组需要一段连续的存储空间，数据太大时可能使用的不是连续存储数据结构。
Java 代码实现
1. 循环实现
public static int binarySearch(int[] data, int target) {
int low = 0;
int high = data.length - 1;
int middle = 0;
// low > high：说明data为空
if (low > high || target < data[low] || target > data[high]) {
return -1;
}
while (low <= high) {
middle = (low + high) / 2;
if (data[middle] > target) {
high = middle - 1;
} else if (data[middle] < target) {
low = middle + 1;
} else {
return middle;
}
}
return -1;
}
2. 递归实现
public static int recursiveBinarySearch(int[] data, int target, int low, int high) {
if (low > high || target < data[low] || target > data[high]) {
return -1;
}
int middle = (low + high) / 2;
if (data[middle] > target) {
return recursiveBinarySearch(data, target, low, middle - 1);
} else if (data[middle] < target) {
return recursiveBinarySearch(data, target, middle + 1, high);
} else {
return middle;
}
}
