二分查找，也称为折半查找，是一种在有序数组中查找特定元素的高效算法。其基本思想是每次将查找范围缩小一半，直到找到目标元素或确定目标元素不存在。
以下是二分查找的详细步骤：
- 初始化左右边界：将初始查找范围设置为整个数组，即
left = 0，right = array.length - 1。 - 计算中间元素的索引：
mid = (left + right) / 2。 - 检查中间元素是否是目标元素：
- 如果
array[mid] == target，则找到目标元素，返回mid。 - 如果
array[mid] < target，说明目标元素在右半部分，更新left = mid + 1。 - 如果
array[mid] > target，说明目标元素在左半部分，更新right = mid - 1。
- 重复步骤2和步骤3，直到找到目标元素或左边界大于右边界
代码
public class BinarySearch { // 二分查找函数 public static 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] < target) { // 目标元素在右半部分 left = mid + 1; } else { // 目标元素在左半部分 right = mid - 1; } } // 目标元素不存在 return -1; } public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int target = 7; int result = binarySearch(array, target); if (result != -1) { System.out.println("目标元素 " + target + " 在数组中的索引为 " + result); } else { System.out.println("目标元素 " + target + " 不存在于数组中"); } } }
这段代码演示了如何使用二分查找在有序数组中查找目标元素。在 main 方法中，我们定义了一个有序数组 array，并在其中查找目标元素 target。最后输出结果，指示目标元素是否存在以及其索引位置。
优缺点
优点：
- 时间复杂度低： 二分查找的时间复杂度是 O(log n)，相比线性搜索 O(n)，在大型有序数据集上具有更高的效率。
- 简单清晰： 算法逻辑相对简单，易于理解和实现。
- 节省空间： 二分查找通常只需要很少的额外空间，主要用于存储左右边界、中间索引等变量。
缺点：
- 仅适用于有序数据： 二分查找要求数据集是有序的，如果数据集无序，需要先进行排序，这可能增加额外的时间复杂度。
- 不适用于链表： 二分查找需要随机访问，对于链表这样的数据结构，二分查找的效率较低，因为它无法直接跳到中间元素。
- 只能查找单一元素： 二分查找适用于查找单一元素的情况，如果需要查找多个匹配的元素，可能需要其他算法。
- 不适用于动态数据集： 如果数据集经常发生变化，频繁的插入和删除可能会导致数组重新排序，使得二分查找的优势减弱。
总体来说，二分查找是一种非常有用的算法，尤其适用于有序数据集的查找操作。然而，使用前需要考虑数据集的特点和操作需求，以确保选择最适合的算法。
其他的用途
在实际应用中，二分查找常常用于：
- 搜索： 在有序数组中快速查找某个元素的索引。
- 算法优化： 在某些算法中，通过二分查找可以提高搜索效率，例如在分治算法中。
- 数据库操作： 在数据库索引的查找过程中，二分查找也有着广泛的应用。
- 游戏开发： 在有序数组或有序集合中查找元素，如查找排行榜中的玩家。
总体来说，二分查找在需要高效搜索有序数据集的情况下是非常有用的。
与他类似的查找
- 线性查找（Linear Search）：
- 特点： 顺序遍历数据集，逐个比较元素，直到找到目标或遍历完整个数据集。
- 适用场景： 数据集无序或未排序，或者需要查找的元素在数据集中的位置相对较靠前。
- 哈希查找（Hashing）：
- 特点： 使用哈希函数将元素映射到一个索引，快速定位元素。
- 适用场景： 适用于需要快速查找、插入和删除的情况，但要求数据结构具有哈希函数的支持。
- 插值查找（Interpolation Search）：
- 特点： 根据目标值的估计位置进行查找，适用于有序且均匀分布的数据集。
- 适用场景： 数据集有序且均匀分布时，插值查找可能比二分查找更快。
- 树结构查找（二叉搜索树、平衡二叉搜索树、B 树等）：
- 特点： 使用树结构进行有序数据的查找，支持高效的查找、插入和删除操作。
- 适用场景： 适用于需要频繁的插入和删除操作，同时要求有序性的数据集。
- 线性索引查找（例如块索引）：
- 特点： 使用索引结构，将数据集分块，通过索引快速定位块，然后再在块内进行查找。
- 适用场景： 适用于大型数据集，其中块的数量相对较小，但每个块中的元素数量较大。
我的其他博客
什么情况下会产生StackOverflowError（栈溢出）和OutOfMemoryError（堆溢出）怎么排查-CSDN博客
