作者：我是80初 | 来源：互联网 | 2024-11-14 13:24
二分查找是一种高效的搜索算法，适用于有序数据集合。其核心思想是通过不断将查找区间缩小一半，直至找到目标元素或区间为空。本文将详细介绍二分查找的基本原理、实现方法以及应用场景的局限性。
二分查找基本原理
二分查找针对的是一个有序的数据集合，其思想类似于分治策略。每次通过与区间的中间元素进行比较，将待查找的区间缩小为原来的一半，直到找到目标元素或区间为空。
二分查找是一种非常高效的查找算法。假设数据大小为n，每次查找后数据都会缩小为原来的一半，即除以2。最坏情况下，直到查找区间被缩小为空才停止。
这是一个等比数列。当n/2^k = 1时，k的值就是总共缩小的次数。每次缩小操作只涉及两个数据的比较，因此经过k次区间缩小操作，时间复杂度为O(k)。通过n/2^k = 1，可以求得k = log₂n，所以时间复杂度为O(log n)。
例如，在42亿个数据中用二分查找一个数据，最多需要比较32次，体现了其高效性。
二分查找的实现
最简单的情况是有序数组中不存在重复元素，用二分查找值等于给定值的数据。
Java二分查找模板：
public int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid]
其中，left、right和mid分别表示数组的左边界、右边界和中间位置。通过比较array[mid]与target的大小，更新接下来要查找的区间范围，直到找到目标元素或区间为空。
实现二分查找的常见错误
1. 循环退出条件
注意循环退出条件是left <= right，而不是left
2. 中间值的计算
如果left和right较大，两者之和可能溢出。改进的方法是将中间值的计算方式改为left + (right - left) / 2。为了进一步优化性能，可以使用位运算left + ((right - left) >> 1)，因为计算机处理位运算比除法运算更快。
3. 边界的更新
模板中，left = mid + 1，right = mid - 1。注意这里的+1和-1，如果直接写成left = mid或right = mid，可能会导致死循环。例如，当right = 3，left = 3时，如果array[3]不等于target，就会导致无限循环。
实际上，二分查找除了用循环实现，还可以用递归实现。
Java递归二分查找模板：
public int binarySearch(int[] array, int target) {
return binarySearchInternally(array, 0, array.length - 1, target);
}
private int binarySearchInternally(int[] array, int left, int right, int target) {
if (left > right) return -1;
int mid = left + ((right - left) >> 1);
if (array[mid] == target) {
return mid;
} else if (array[mid]
二分查找的应用场景及局限性
1. 依赖顺序表结构
二分查找依赖于顺序表结构（如数组），因为需要按索引随机访问元素。链表不支持随机访问，因此不适合使用二分查找。
数组按索引随机访问的时间复杂度为O(1)，而链表随机访问的时间复杂度为O(n)。如果数据存储在链表中，二分查找的时间复杂度会变得很高。
二分查找只能应用于通过顺序表存储的数据结构。如果数据存储在其他数据结构中，则无法使用二分查找。
2. 适用于有序数据
二分查找仅适用于有序数据。它适合于插入、删除操作不频繁且一次排序多次查找的场景。对于动态变化的数据集，二分查找不再适用。
3. 数据量较小不适合
只有数据量较大时，二分查找的优势才会明显。但对于数据量较小的情况，顺序遍历可能更为简单高效。
然而，如果数据之间的比较操作非常耗时，无论数据量大小，都推荐使用二分查找，因为它能显著减少比较次数，提高性能。
例如，数组中存储的都是长度超过300的字符串，两个长字符串之间的比较非常耗时。在这种情况下，二分查找比顺序遍历更有优势。
4. 数据量过大也不适合
二分查找依赖于数组这种数据结构，而数组要求内存空间连续，对内存的要求较高。
例如，如果有1GB大小的数据，需要用数组存储，就需要1GB的连续内存空间。即使有2GB的内存空间，但如果这些空间是零散的，没有连续的1GB大小的内存空间，也无法申请一个1GB大小的数组。因此，对于大数据量，二分查找可能会遇到内存问题，不适用。
京公网安备 11010802041100号