Doubt binary search c++

Asked

Viewed 556 times

0

https://www.codepit.io/#/problems/5369c33df6fa9de49e5c7d0e/view? index=1

I managed to resolve this issue as follows:

#include <iostream>
#include <algorithm>
using namespace std;

int contar_pares(int y, int x[], int tam){
    int cont = 0;
    for(int i = tam; i > 0; i--){
        for(int j = tam - 1; j >= 0; j--){
            if(x[i-1] - x[j] == y){
               cont++;
            }
        }
    }
    return cont;
}

int main(){
    int n, k;
    cin >> n >> k;
    int tamanho = n;
    int vetor[tamanho];
    for(int i = 0; i < tamanho; i++){
        cin >> vetor[i];
    }
    sort(vetor, vetor + tamanho);
    cout << contar_pares(k, vetor, tamanho) << endl;

    return 0;
}

But when I submit the time limit exceeded... Some of my colleagues managed to solve it with binary search, but my question is: how do I count how many times the k will be found inside a binary search?

c++

  • Better than a binary search is using a set as if it were a hashtable, which even takes advantage of the resources that c++ gives it, and plays with the constraints of the problem that indicate that the numbers are distinct and do not repeat. It also increases the time complexity from O(nlogn) to O(n), and in the example of its code is O(n 2). Example of solution using set.

1 answer

2

To use binary search, you first need to sort the array of elements. This will download the complexity of O(n2) - your solution - to O(n log n) (ordering complexity, using quicksort, for example). To count the number of occurrences of the difference, do a binary search for n+k in the ordered array (where n is the number you are counting the differences at the time and k the difference). If you find the element, increment the counter.

However, as @Isac said in the comment, this is still not the best option - the solution proposed by him solves the problem faster, without having to sort the elements, reducing the speed complexity to O(n).

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.