修改二进制搜索找到比该键的下一个大项目 [英] modify binary search to find the next bigger item than the key

问题描述

我想修改的著名二进制搜索算法返回下一个大项目的索引而不是被搜查的关键。

I want to modify the famous binary search algorithm to return the index of the next bigger item instead of the key being searched.

因此​​，我们有4个情况：

So we have 4 cases:

1. 关键是比所有项目小，返回0。
2. 关键是大于一切的物品，返回items.length。
3. 的关键是找到在指数X，返回X + 1。
4. 关键是没有找到，返回的下一个更大的一个指标。

例如：

data = { 1, 3, 5, 7, 9, 11 };

• 搜索0返回0。
• 搜索11或12的回报6。

• 搜索5或6的回报3。

  • search for 0 returns 0.
  • search for 11 or 12 returns 6.

  • search for 5 or 6 returns 3.

    while (low <= high) {
        mid = (low + high) / 2;
        if (data[mid] < val)
            low = mid + 1;
        else if (data[mid] > val)
            high = mid - 1;
        else {
            break;
        }
    }
    

  目前得到它的工作通过检查低值和高值。 有没有什么有趣的code这样做！

  Currently got it working by examining low and high values. Is there any interesting code to do so!

  EDIT！

  下面是我如何得到它的工作：

  here is how I get it working:

      if (low <= high)
          found = (low + high) / 2 + 1;
      else if (low >= data.length)
          found = data.length ;
      else if (high < 0)
          found = -1;
      else
          found = low;
  

  我要寻找一个更优雅的方式！

  I am looking for a more elegant way!

  编辑II！

  这code的作品，如果没有重复。 处理重复的情况下，我们需要修改的第一个，如果条件：

  this code works if no duplicates. to handle the case of duplicates we need to modify the first if condition:

  if (low <= high)
      found = (low + high) / 2 + 1;
  

  迭代，直到找到一个更大的元素。

  to iterate until it finds a bigger element.

  推荐答案

  警告 - 这是一个不好回答，我现在无法删除，因为它已被接受。下面code是如下所述，但是这不是问题问什么 - 它看起来像我没有阅读问题正确。我现在无法删除，因为它是公认的。

  WARNING - This is a bad answer that I now can't delete because it was accepted. The following code is as described below, but that's not what the question asks for - it looks like I didn't read the question properly. I can't delete this now because it's accepted.

  下面code发现比目标键键更大的第一个项目...

  The following code finds the first item with key greater than the target key...

  while (upperbound > lowerbound)
  {
    testpos = lowerbound + ((upperbound-lowerbound) / 2);
  
    if (item[testpos] > goal)
    {
      //  new best-so-far
      upperbound = testpos;
    }
    else
    {
      lowerbound = testpos + 1;
    }
  }
  

  这是一个从这个答案，它试图解释一个比较每一次迭代的二进制搜索，以及如何引用适应它。

  It's quoted from this answer, which tries to explain the one-comparison-per-iteration binary search and how to adapt it.

  这篇关于修改二进制搜索找到比该键的下一个大项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！