Binary Search with Duplicates-CodePudding

I am doing this particular exercise where I have to implement the Binary Search algorithm which returns the index of the first occurence of an element in a sorted array, if it contains duplicates. Since I am primarily working on my algorithmic skills in C , I am only trying to do it in C . Here is my code:

#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) << ' ';
  }
}

The first input to the program tells how many items the array should contain, the second is the enumeration of these elements, third line tells how many keys to search for and the final line are the individual keys. The output is the indices for the key or -1 when no such key is found.

My strategy is to use a function to find the index of a key. If it is found, then in case of duplicates, the first occurrence has to have a lower index. That is what the first_occurence() method does; keep looping back till the first occurence is found.

For the following input:

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

The output is:

-1 4 -1 -1 -1

Which is only correct for the key 7. I have been trying to debug this for quite some time but I can not figure out the problem.

CodePudding user response：

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

Your binary search algorithm requires that the data is sorted before you call it.

Example:

#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';
    }
}