您的位置: 首页  >  文章  >  二进制搜索详细

二进制搜索详细

分类: 文章 • 2024-12-01 11:49:52
二进制搜索详细

我希望我们都对什么是二进制搜索有所了解。 但是，我不会逐步解释算法，而是会深入了解二进制搜索的工作原理和用法。

如果您不知道Binary Search，请查看： geeksforgeeks.org/binary-search 。

给定一个排序后的数组，我们找到最中间的元素，并用键检查该元素。 如果最中间的元素等于key，我们就找到了key。 如果最中间的元素大于键，则在最中间的元素的左半部分搜索，否则我们在右半部分搜索。

这是Java中二进制搜索的迭代代码

注意，在第6行中，我们使用 

int mid = (low + high) / 2;

但是以这种方式进行中间计算是无效的。 为什么？ 让我们举个例子。
让我们采用从低整数到高整数（包括两者）的整数。

请注意在第3列和第4列中由公式计算的中点。

  • 对于低= 3和高= 11，元素（#elements）的数量= 9
    因此只有1个中点，即7
    *两个公式都正确计算了中间值
  • 对于低= 3和高= 10，＃元素= 8
    因此有2个中点，6个（较低的中点）和7个（较高的中点）
    *两个公式都正确计算了下中点
  • 对于低= -11和高= -3，＃elements = 9
    因此只有1个中点，即-7
    *两个公式都正确计算了中间值
  • 对于低= -10和高= -3，＃元素= 8
    因此有2个中点，-7（下中点）和-8（上中点）
    *公式(low + high) / 2未能正确计算下中值，但另一个公式已正确计算出它。

因此，我们应该始终使用以下公式来计算较低的中点，因为它更可靠： 

int mid = low + ((high - low)/2);

当#elements =奇数时，我们只有1个中点。 因此，我们可以使用上述公式来计算中间值。
当#elements =偶数时，以上公式仅给出较低的中点。
较高的中值可以通过以下公式计算： 

int mid2 = low + ((high - low + 1) / 2);

现在，有趣的部分...

让我们回到二进制搜索的迭代代码。 注意三件事。
1.我们如何上下移动
2.我们如何进行中间计算
3. while循环中的条件

Binary Search的优点仅在于这三件事。 让我们进一步探讨。

对于简单的二进制搜索，我们只需要在数组中查找元素，
我们使用以下内容：
1. low = mid - 1表示low
2. high = mid + 1 ，代表high
3. mid = low + ((high - low) / 2) （为什么？如上所述）
4. low <= high ，而while循环

我们总是使用相同的条件进行二进制搜索吗？
这取决于……我们的问题陈述。

范例1：

给定一个整数x，在满足条件y <= x的大小为N的数组中找到最大元素y

解：

我们知道x可能不在数组中。 因此，在给定数组中对x进行简单的二进制搜索将不起作用。 但是对于二进制搜索，我们所知道的只是x，即键。 我们需要在数组中找到最接近x且小于或等于x（如果存在）的元素。

使用二进制搜索时，您始终应该想到三件事：
1.我们应该如何上下移动？
2.我们应该如何计算中位数？
3. while循环中的条件是什么？

我们总是从“如何上下移动？”开始。 然后找出如何计算中点以及while条件。 并非相反。

  1. 如何上下移动？
    当array[mid] < x ，当前元素可能是答案（因为y可以小于x）。
    因此，我们不应在走低时放弃中间位置。
    因此，低变为low = mid ，而不是low = mid + 1
    高仍然是相同的，与我们的问题陈述无关。
  2. 如何计算中位数？
    当我们使用mid = low + ((high - low) / 2) ，我们正在计算较低的mid。 因此，当数组中的#elements为偶数时，
    if(array[mid] > x)变为false，因此控制将转到else子句，其中low = mid 。 这导致无限循环。 （为什么？举个例子）
    因此，我们采用较高的中值，即mid = low + ((high - low + 1) / 2)
  3. while循环中的条件是什么？
    由于我们在low中存储小于或等于x的最大元素，因此当low = high时应停止并返回array[low]或array[high] 。 因此，while循环中的条件为low < high 。

Java中的解决方案如下所示：

范例2：

给定整数x，在大小为N的数组中找到满足条件y >= x的最小元素y

解：

使用我们在示例1中使用的类似分析方法（自己尝试），我们可以说

  1. low = mid + 1表示低
  2. high = mid移高
  3. mid = low + ((high - low) / 2)用于计算中
  4. low < high适用于while循环中的条件

因此，我们可以将使用Binary Search的不同情况列表如下：

随时尝试这些条件，希望您对如何使用二进制搜索有所了解。

Namaste！

From: https://hackernoon.com/binary-search-in-detail-914944a1434a

相关推荐