二分查找中的首次出现

Question

我正在调试一些代码，然后发现了一个以前不知道的事情。普通的二分查找会在数据集中返回一个键出现多次的随机索引。我如何修改下面的代码以返回第一个出现的位置？这是人们经常做的吗？

//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
    return bSearchVal(a, 0, a.length, key);
}

private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                                 int toIndex, long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid].val;

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return (low); // key not found. return insertion point
}

- Amir Afghani

---

酷啊 - 我可以在自己的问题和答案中刷声望了... https://dev59.com/oVTTa4cB1Zd3GeqPpyzG 解释了一种二分查找的形式，可以找到第一个大于或大于等于的项，或者最后一个小于或小于等于的项。 - user180247

哈哈，谢谢！我会看一下的。偶尔我会注意到这样的事情，然后想“你什么都不知道”。 - Amir Afghani

Answer 1

Jon Skeet的回答中有一个补充：

实现更快的方法其实并不难，只需要加入两行代码即可，以下是我的实现方式：

    if (midVal < key)
        low = mid + 1;
    else if (midVal > key)
        high = mid - 1;
    else if (low != mid) //Equal but range is not fully scanned
        high = mid; //Set upper bound to current number and rescan
    else //Equal and full range is scanned
        return mid;

- bezmax

---

你会如何修改代码，使其适用于最后一个索引而不是第一个索引？ - Amir Afghani

简单地反转高低值（未测试是否有效）：.... else if (high != mid) low = mid; else return mid; - bezmax

第一项：mid = (unsigned int) floor((low + high) / 2.0); 最后一项：mid = (unsigned int) ceil((low + high) / 2.0); - Vaibhav Bajpai

@bezmax，我需要你的一点帮助... 我想知道这段代码是否比此链接中的代码更快 https://www.hackerearth.com/notes/searching-code-monk/ 请查看第一个出现的代码。 - Ashwani Kumar Rahul

@VaibhavBajpai 这在哪里/如何适用? - jedierikb

https://dev59.com/hW3Xa4cB1Zd3GeqPeWkk - jedierikb

Answer 2

当找到匹配的值后，您基本上需要沿着集合向上查找，直到找到一个与之不匹配的条目。

您可以通过立即获取低于要查找的键的索引，然后在两者之间进行二分查找来使其更快 - 但我可能会选择更简单的版本，除非您有大量相等的条目，否则这种方法已经足够高效了。

- Jon Skeet

---

嗨Jon - 所以else子句中需要一个while循环？我明白这个想法，但它似乎看起来很不协调，不是吗？ - Amir Afghani

顺便说一下，我是你的忠实粉丝。感谢迄今为止的回复。 - Amir Afghani

@Amir：这当然是一种方法。另一种方法是保留原始方法（最好更改名称 :)），但提供另一种方法来查找第一个方法，通过调用原始方法，然后执行while循环（如果没有匹配项）。请注意，在我使用的API中，插入点以负值（使用〜）返回，以指示未找到该值，但同时也指示插入点。 - Jon Skeet

这个解决方案的时间复杂度为O(N)，因为可能有多达N个具有您正在搜索的值的元素。 - Juan Martinez

@JuanMartinez：因此，在答案的结尾处加上了“除非您有大量相等的条目，否则足够高效”的一句话。 - Jon Skeet

Answer 3

如果您的数据全部是整数，那么这个技巧可以帮助您。它使用浮点数组来存储值。

float array[];    //contains all integral values
int searchValue;

int firstIndex = -(binarySearch(array, (float)searchValue - 0.5F) + 1);

它的基本作用是查找搜索值和其前面整数之间的插入索引。由于所有值都是整数，它会找到搜索值的第一次出现。

此外，它的运行时间为 log(n)。

示例：

import java.util.Arrays;

public class BinarySearch {
    // considering array elements are integers
    float ar[] = new float[] { 1, 2, 3, 3, 4, 4, 5, 9, 9, 12, 12 };

    public void returnFirstOccurrence(int key) {
        int firstIndex = -(Arrays.binarySearch(ar, key - 0.5F) + 1);
        if (ar[firstIndex] != key)
            System.out.println("Key doesn't exist");
        else
            System.out.println("First index of key is " + firstIndex);
    }

    public static void main(String Args[]) throws Exception {
        new BinarySearch().returnFirstOccurrence(9);
    }

}

输出: 7

附注：我在几次编程比赛中使用过这个技巧，每次都很好用。

- Arnab

---

你能解释一下吗？这是如何获取第一个出现的索引？ - nawfal

Java集合框架中的二分查找实现会返回数字的索引，或者如果数字不存在，则返回可以插入数字的位置的索引。请参见链接。此外，我已经编辑了一个示例。 - Arnab

明白了。这不仅仅是 hacky，而且非常 hacky :) 它只适用于整数，但仍然需要一个 float[] 来保存它们。如果客户最初有一个 int[]，那么创建一个新的 float[] 可能会有一些费用。你可能想要将这两个条件 以粗体字写出来 :) - nawfal

就像我之前所说的，我只在比赛中使用它。我是一名学生，没有任何工业经验，但我同意在生产代码中使用它会非常不合适和令人困惑。 - Arnab

在生产中使用这种解决方案比在int[]上使用一些临时算法更好...如果您只执行一次此操作，则存在O(n)的转换成本，但是如果从一开始就将数组创建为float[]并在程序的生命周期内维护它，并多次运行搜索，则不会有显着的性能差异。 - mcvkr

你的示例代码存在两个问题。第一，如果 firstIndex == ar.length（因为 key > ar[ar.length-1]），这会抛出异常。第二，ar[firstIndex] != key 是有风险的，因为你不应该使用 == 或 != 来比较浮点数。 - Ricola

Answer 4

通过更加精准的匹配定义，您可以改进现有的搜索算法。在序列1、3、5、5、5、9中，您可以发现高亮显示的数字5是第一个匹配项，因为它前面的数字3比5小。因此，如果mid落在与键相等的数组元素上，则只有当a [mid-1]小于键时才将其视为匹配项，而其他相等的数组元素则被视为大于元素。现在您的算法变为（包括Jon Skeet的建议返回插入点的负值）：

public static int binarySearch(int[] a, int key) {
    int low=0,high=a.length-1;
    while (low<=high) {
        int mid=(low+high) >>> 1;
        int midVal=a[mid];
        if (midVal < key) 
            low=mid+1;
        else if (mid>0 && a[mid-1]>=key) //we already know midval>=key here
            high=mid-1;
        else if (midVal==key) //found the 1st key 
             return mid;
        else
            return ~mid;      //found insertion point
    }
    return ~(a.length);       //insertion point after everything
}

它使用了更多的比较，但在我的基准测试中比Stev314的版本运行得更快，可能是因为缓存效应。

- paperhorse

Answer 5

你可以使用“下界算法”来代替二分查找。这种算法在例如C++/STL中使用，并且将其转换为Java很简单。下界算法的时间复杂度也是O(log n)，与二分查找相同。这比首先使用二分查找，然后线性搜索第一个匹配元素要好 - 这将具有最坏情况行为O(n)。请注意保留HTML标记。

- Jiri Kriz

---

尽管在C++库中被称为下限，但它仍然是一种二分查找算法——至少根据我手头的Niklaus Wirth所著《算法与数据结构》（Modula 2版）一书。也许这只是一个观点问题，不同算法和相同算法的变体之间的界限在哪里。 - user180247

许多（大多数？）库（例如C、C++/STL、Java）实现的“二分查找”在存在多个键时并未指定返回哪个索引。这也是所提出问题的问题所在。“下界”明确指定了结果。 - Jiri Kriz

同意，但库函数的良好命名并不一定与算法教材中相同，特别是当库可能有几个变体时。顺便说一句，我并不是想说你关于任何事情都是错的，我已经为你的答案点赞了。 - user180247

Answer 6

以下算法使用二分查找，查找第一个键大于或等于您的搜索键的项...

while (upperbound > lowerbound)
{
  testpos = lowerbound + ((upperbound-lowerbound) / 2);

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

这不是针对我不太熟悉的Java编写的，因此可能需要进行微小的调整。请注意，边界是半开放的（下限包含上限不包含），这对于正确性非常重要。

这可以适应其他类似的搜索-例如查找最后一个key <= 搜索值。

这与我早期的问答这里略有修改。

- user180247

---

虽然扩展很简单，但我想指出OP想要第一次出现的是“等于”，而不是“大于或等于”。 - nawfal

Answer 7

一种方法是在整个二分搜索过程中保持不变量。在您的特定情况下，不变量将是：

• array[low] < key
• key <= array[high]

然后，您可以使用二分搜索来最小化低位和高位之间的差距。当low + 1 == high时，high将是答案。C++示例代码：

// check invariant on initial values.
if (array[low] >= key) return low;
if (array[high] < key) return high+1;
// low + 1 < high ensures high is at least low + 2, thus
// mid will always be different from low or high. It will
// stop when low + 1 == high.
while (low + 1 < high) {
  int mid = low + (high - low) / 2;
  if (array[mid] < key) {
    low = mid;   // invariant: array[low] < key
  } else {
    high = mid;  // invariant: array[high] >= key
  }
}
return high;

这段代码与你的示例代码不同之处在于更新low和high时仅更新到mid，而不是mid+1或mid-1。因为我们已经检查了array[mid]的值，所以可以保证在更新边界时仍然满足不变量。在开始搜索之前，您需要检查初始值上的不变量。

- pherl

Answer 8

这是我使用二分查找在已排序数组中获取具有多个出现的键的较低索引的解决方案。

int lowerBound(int[] array,int fromIndex, int toIndex, int key)
{
    int low = fromIndex-1, high = toIndex;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]< key) low=mid;
        else high=mid;
    }
    int p = high;
    if ( p >= toIndex || array[p] != key )
        p=-1;//no key found
    return p;
}

我们需要对这段代码进行一些修改，以使其适用于上限，使用二分查找，因此这是代码的工作副本。

 int upperBound(int[] array,int fromIndex, int toIndex, int key)
{
    int low = fromIndex-1, high = toIndex;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]> key) high=mid;
        else low=mid;
    }
    int p = low;
    if ( p >= toIndex || array[p] != key )
        p=-1;//no key found
    return p;
}

- rykhan

Answer 9

在这个线程中，您可以找到二分搜索的完整示例（递归版本），以及另外两个版本（基于原始版本），允许您获取给定键的第一个索引和最后一个索引。

为了方便起见，我添加了相关的Junit测试。

- Naor Bar

Answer 10

我认为一个更简单的方法是将最新的mid索引存储在结果变量中，然后继续运行二分搜索。

这是Swift代码：

func first<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { hi = mid - 1; res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}

此外，如果您要查找键的最后一个索引，则只需要进行非常小的更改（仅一行）。

func last<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { lo = mid + 1;  res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}

- HepaKKes