Doubt binary search c ++

0

I was able 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 timeout exceeded ... Some of my colleagues were able to solve with binary search, but my question is: how do I count how many times k will be found within a binary search?

    

asked by anonymous 21.09.2018 / 03:07

1 answer

2

To use binary search, you first need to sort the array of elements. This will lower the complexity of O (n 2 ) - your solution - to O (n log n) (order 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 that you are counting the differences in the moment 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 it solves the problem in a way faster, without having to sort the elements, reducing the speed complexity for O (n).

    
21.09.2018 / 19:36