Java中的二进制搜索：递归、迭代和Java集合

　　Java中的线性搜索一直是在数组中查找元素的首选方法。它按顺序搜索数组的每个元素，并且非常容易实现。但是，当所讨论的数组包含数万个元素时，线性搜索的缺点是显而易见的。在这种情况下，Binary Search实现的“分而治之”方法对于具有时间和空间复杂性的程序员来说更加有效和可取。

　　二进制搜索

　　在二进制搜索中，数组被反复分成两半，直到找到键(正在搜索的元素)。分割是虚拟的，即保持数据的完整性。每次迭代时，数组的中间值都是集中的。如果该值等于我们正在寻找的键，则循环或递归函数终止。否则，它会继续循环。如果中间值大于键，则该函数将焦点放在数组的前半部分，反之亦然。重复此过程，直到找到密钥或循环访问整个阵列。

　　线性搜索和二进制搜索之间的区别

　　二进制搜索算法

　　二进制搜索的算法如下。

　　确定阵列的第一个点和最后一个点。每次迭代时，这些点将根据数组和正在搜索的键进行调整。

　　循环访问数组并比较当前第一个点和最后一个点之间的中间值。在第一次迭代中，第一个和最后一个变量将与数组中的实际变量相同。

　　如果键大于中间值，则该值的索引将存储在新的“First”变量中。

　　如果键小于中间值，则该值的索引将存储在“Last”变量中。

　　重复此条件，直到以下两个条件之一变为真：

　　找到密钥。

　　已迭代整个数组。

　　下面给出了迭代二进制搜索和递归二进制搜索的代码。

　　迭代二进制搜索

　　下面给出了使用迭代方法进行二进制搜索的代码。

　　递归二进制搜索

　　下面给出了使用递归的二进制代码。

　　时间复杂度

　　随着每次迭代的传递，数组(即搜索空间)被拆分一半。每次迭代“m”后，搜索空间的大小将更改为N / 2m。在最坏的情况下，我们只会在数组的一个远端留下一个元素。此时，二进制搜索的复杂性将是 k = log2N。线性搜索的时间复杂度为O(N)，这导致二进制搜索的速度比O(log2N)复杂度快得多。这是使用二进制搜索而不是线性搜索的主要好处。

　　空间复杂性

　　二进制搜索使用三个不同的变量 - 开始，结束和中间。这三个变量被创建为指向数组索引的内存位置的指针。因此，二进制搜索在空间方面非常有效。迭代二进制搜索的空间复杂度为 O(1)。对于递归实现，它是 O(log N)。