Java二分查找算法的例子

在二分查找法中，将集合反复分成两半，根据关键字是小于还是大于集合的中间元素，在集合的左半边或右半边查找关键元素。

一个简单的二进制搜索算法如下：

计算集合的中间元素。

将关键项与中间元素进行比较。

如果 key = middle 元素，那么我们返回找到的键的中间索引位置。

Else 如果 key > mid 元素，则 key 位于集合的右半部分。因此，在集合的下半部分(右)重复步骤 1 到 3。

else key < mid element，则key在集合的上半部分。因此，您需要在上半部分重复二进制搜索。

从上面的步骤可以看出，在二分查找中，第一次比较后，集合中有一半的元素被忽略了。

请注意，相同的步骤序列适用于迭代和递归二分查找。

让我们用一个例子来说明二分查找算法。

例如，采用以下包含 10 个元素的排序数组。

让我们计算数组的中间位置。

中 = 0+9/2 = 4

#1) 键 = 21

首先，我们将键值与 [mid] 元素进行比较，我们发现 mid = 21 的元素值。

因此我们发现 key = [mid]。因此，密钥位于数组中的位置 4。

#2) 键 = 25

我们首先将键值与mid进行比较。由于 (21 < 25)，我们将直接在数组的上半部分搜索键。

现在我们将再次找到数组上半部分的中间值。

中 = 4+9/2 = 6

位置 [mid] 的值 = 25

现在我们比较 key 元素和 mid 元素。所以 (25 == 25)，因此我们在位置 [mid] = 6 找到了密钥。

因此，我们反复划分数组，通过比较关键元素和中间元素，我们决定在哪一半中搜索关键。二进制搜索在时间和正确性方面更有效率，而且速度也快得多。