带重复项的二分查找

Question

我正在做这个特殊的练习，我必须实现二进制搜索算法，该算法 returns 排序数组中元素第一次出现的索引，如果它包含重复项。由于我主要在 C++ 中研究我的算法技能，所以我只尝试在 C++ 中进行。这是我的代码：

#include <iostream>
#include <cassert>
#include <vector>

using std::vector;

int binary_search(const vector<int> &a, int x, int n) {
  int left = 0, right = n-1; 

  while(left<= right){
    int mid = left + (right-left)/2;
    if(x== a[mid]){
      return mid;
    }else if(a[mid]>x){
      right = mid-1;
    }else{
      left = mid+1;
    }
  }
      return -1;
}


int first_occurence(const vector<int>&a, int x, int n) {
  int out = binary_search(a, x, n);
  if(out !=-1){
     for(int i = out;i>0&& a[i]==x;--i ){
        out = i;
     }
  }
  return out;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  int m;
  std::cin >> m;
  vector<int> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i];
  }
  for (int i = 0; i < m; ++i) {
    std::cout << first_occurence(a, b[i], n) << ' ';
  }
}

程序的第一个输入告诉数组应该包含多少项，第二个是这些元素的枚举，第三行告诉要搜索多少个键，最后一行是单个键。输出是键的索引，如果找不到这样的键，则输出 -1。

我的策略是使用函数查找键的索引。如果找到，则在重复的情况下，第一次出现的索引必须较低。这就是 first_occurence() 方法的作用；继续循环直到找到第一个出现的地方。

对于以下输入：

10
1 5 4 4 7 7 7 3 2 2
5
4 7 2 0 6

输出为：

-1 4 -1 -1 -1

这只对密钥 7 是正确的。我已经尝试调试它很长时间了，但我无法找出问题所在。

Answer 1

returns the index of the first occurence of an element in a sorted array,

您的二进制搜索算法要求在您调用它之前对数据进行排序。

示例：

#include <algorithm>
#include <sstream>

int main() {
    std::istringstream in(R"aw(10
1 5 4 4 7 7 7 3 2 2
5
4 7 2 0 6
)aw");

    int n;
    in >> n;
    vector<int> a(n);
    for (auto& v : a) {
        in >> v;
    }

    std::sort(a.begin(), a.end());               // <- add this

    // display the sorted result:
    for (auto v : a) std::cout << v << ' ';
    std::cout << '\n';

    int m;
    in >> m;
    vector<int> b(m);
    for (auto& v : b) {
        in >> v;
    }
    for (auto v : b) {
        std::cout << v << ' ' << first_occurence(a, v, n) << '\n';
    }
}

带重复项的二分查找

Binary Search with Duplicates

c++

search

binary-search