二进制搜索范围 [英] Binary search bounds

问题描述

我总是最艰难的时光，而且我还没有看到关于所谓的如此普遍和高度使用的东西的明确解释。

我们已经知道标准二进制搜索。给定开始的上限和下限，找到中间点（lower + high）/ 2，然后将其与数组进行比较，然后相应地重新设置界限，依此类推。

但是，要调整搜索以查找（按升序排列的列表），有什么区别：

1. 最小值> =目标


2. 最小值>目标


3. 最大值< =目标


4. 最大值< target

似乎每种情况都需要对算法进行很小的调整，但我永远无法使它们正常工作。我尝试更改不平等，返回条件，更改边界的更新方式，但是似乎没有什么一致。

处理这四种情况的确切方法是什么？

解决方案

二进制搜索（至少是我实现它的方式）依赖于一个简单的属性-谓词在区间的一端有效，并且另一端不成立。我一直认为我的区间在一端关闭，在另一端打开。因此，让我们看一下这段代码片段：

  int beg = 0; // pred（beg）应当为true 
 int end = n; //数组的长度或保证超出我们对
 
感兴趣的区间的值（end-beg> 1）{
 int mid =（end + beg）/ 2; 
 if（pred（a [mid]））{
 beg = mid; 
} else {
 end = mid; 
} 
} 
 //答案是a [beg] 
  

这将适用于您定义的任何比较。只需将 pred 替换为< = target 或> = target 或<目标或>目标。

在循环退出后， a [beg] 将是给定不等式成立的最后一个元素。 / p>

因此，让我们假设（如注释中所建议的那样）我们要查找 a [i] <=目标的最大数字。然后，如果我们使用谓词 a [i]< =目标，则代码将如下所示：

  int beg = 0; // pred（beg）应该为true 
 int end = n; //数组的长度或一个保证值超出我们对
感兴趣的区间的值while（end-beg > 1）{
 int mid =（end + beg）/ 2; 
 if（a [mid]< = target）{
 beg = mid; 
} else {
 end = mid; 
} 
} 
  

在循环退出后，您所处的索引搜索将是 beg 。

另外，根据比较的不同，您可能必须从右端开始数组。例如。如果您要搜索最大值> =目标，则将执行以下操作：

  beg = -1; 
 end = n-1; 
 while（end-beg> 1）{
 int mid =（end + beg）/ 2; 
 if（a [mid]> = target）{
 end = mid; 
} else {
 beg = mid; 
} 
} 
  

您要搜索的值将是索引 end 。请注意，在这种情况下，我考虑了时间间隔（beg，end] ，因此我对开始时间间隔进行了一些修改。

I always have the hardest time with this and I have yet to see a definitive explanation for something that is supposedly so common and highly-used.

We already know the standard binary search. Given starting lower and upper bounds, find the middle point at (lower + higher)/2, and then compare it against your array, and then re-set the bounds accordingly, etc.

However what are the needed differences to adjust the search to find (for a list in ascending order):

1. Smallest value >= target
2. Smallest value > target
3. Largest value <= target
4. Largest value < target

It seems like each of these cases requires very small tweaks to the algorithm but I can never get them to work right. I try changing inequalities, return conditions, I change how the bounds are updated, but nothing seems consistent.

What are the definitive ways to handle these four cases?

解决方案

Binary search(at least the way I implement it) relies on a simple property - a predicate holds true for one end of the interval and does not hold true for the other end. I always consider my interval to be closed at one end and opened at the other. So let's take a look at this code snippet:

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in

while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (pred(a[mid])) {
    beg = mid;
  } else { 
    end = mid;
  }
}
// answer is at a[beg]

This will work for any of the comparisons you define. Simply replace pred with <=target or >=target or <target or >target.

After the cycle exits, a[beg] will be the last element for which the given inequality holds.

So let's assume(like suggested in the comments) that we want to find the largest number for which a[i] <= target. Then if we use predicate a[i] <= target the code will look like:

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] <= target) {
    beg = mid;
  } else { 
    end = mid;
  }
}

And after the cycle exits, the index that you are searching for will be beg.

Also depending on the comparison you may have to start from the right end of the array. E.g. if you are searching for the largest value >= target, you will do something of the sort of:

beg = -1;
end = n - 1;
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] >= target) {
    end = mid;
  } else { 
    beg = mid;
  }
}

And the value that you are searching for will be with index end. Note that in this case I consider the interval (beg, end] and thus I've slightly modified the starting interval.

这篇关于二进制搜索范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！