Java 中的递归二分查找

二分查找算法是编程中常用的算法之一。它用于在排序数组中搜索和查找元素。

二分查找算法是一种高效的搜索技术，用于在排序的数据集中定位特定元素。它通过不断地将数据集分成两半并比较目标值与中间值来工作，直到找到目标值或确定其不存在。

二分查找基于分治原则，该原则涉及将一个大问题分解为更小、更易于管理的子问题。在二分查找的情况下，大问题是在排序数据集中查找特定元素。然后递归地解决子问题，直到找到目标元素或确定其不存在。

分治原则是一项强大的技术，可用于解决各种各样的问题。

分治原则在编程中是一种解决问题的方法，涉及将一个大问题分解为更小、更易于管理的子问题。然后递归地解决子问题，直到解决原始问题。

• 排序算法，例如快速排序和归并排序
• 搜索算法，例如二分查找
• 字符串处理算法，例如 KMP 算法
• 图算法，例如 Dijkstra 算法和 Prim 算法
• 数值算法，例如快速傅里叶变换 (FFT)

二分查找算法是如何工作的？

二分查找算法是一种分治算法，用于在排序数组中搜索特定元素。

请注意，要使算法有效工作，元素的集合/数组必须是已排序的。

初始化搜索区间。搜索区间是数据集中当前正在考虑的元素范围。最初，搜索区间是整个数据集。

步骤 1：找到搜索区间的中间元素。这是通过计算搜索区间中第一个和最后一个元素的平均值来完成的。

步骤 2：将目标值与中间元素进行比较。如果目标值等于中间元素，则搜索成功，并返回目标元素的索引。

步骤 3：如果目标值小于中间元素，则将搜索区间缩小到原始搜索区间的左半部分。

步骤 4：如果目标值大于中间元素，则将搜索区间缩小到原始搜索区间的右半部分。

步骤 5：重复步骤 2 到 5，直到找到目标元素或搜索区间变为空。

二分查找算法

注意：X 是我们要搜索的元素。

• 将 x 与中间元素进行比较。
• 如果 x 与中间元素匹配，则返回 mid 索引。
• 否则，如果 x 大于中间元素，则 x 只能位于中间元素之后的右半部分子数组中。因此，我们递归地处理右半部分。
• 否则（x 更小），递归地处理左半部分。

BinarySearch.java

输出

Element found at index 3

复杂度

最佳情况：最佳情况下的时间复杂度为 O(1)。最佳情况发生在目标元素是数组的中间元素时。在这种情况下，算法只需要将目标元素与中间元素进行比较，然后返回目标元素的索引。

平均情况：平均情况下的时间复杂度为 O(n)。平均情况发生在目标元素不是数组的中间元素时。在这种情况下，算法需要将数组分成两半，并将目标元素与中间元素进行比较。然后，算法将递归地搜索数组的相应一半。该过程将一直持续到找到目标元素或数组变为空。

最坏情况：最坏情况下的复杂度为 O(n log n)。最坏情况发生在目标元素不在数组中时。在这种情况下，算法将数组分成两半，并将目标元素与中间元素进行比较。然后，算法将递归地搜索数组的相应一半。此过程将一直持续到数组变为空。

二分查找的应用

• 在排序数组中查找元素。
• 确定 n 是否为整数的平方。
• 在给定的排序整数数组中查找大于或等于 x 的第一个值。
• 查找给定目标值在整数数组中的频率。
• 查找先递增后递减的数组的峰值。
• 一个排序数组被旋转了 n 次。在该数组中搜索目标值。
• 实现字典。
• 调试线性代码。
• 确定大型系统的资源需求。
• 在排序集合中查找值。
• 半导体测试程序。
• 方程的数值解。

二分查找的优点

• 与线性搜索等其他搜索算法相比，二分查找具有许多优点。
• 速度：二分查找比线性搜索快得多，尤其是在处理大型数据集时。
• 效率：二分查找比线性搜索更有效，因为它找到目标元素所需的比较次数更少。
• 可靠性：二分查找是一种可靠的算法，因为它始终返回目标元素的正确索引，如果找不到目标元素，则返回 -1。

二分查找的缺点

二分查找的一个缺点是它要求数据集是已排序的。这会增加搜索算法的开销，尤其是在处理大型数据集时。此外，对于小型数据集，二分查找不如线性搜索有效。