C Busca binária em C

[Flavio Daniel]

Boa tarde como eu posso implementar a busca binária neste código em C

 

#include <stdio.h>
#include <stdlib.h>

int main()
{

    int n, qtdeC, i, cont, loc;

    scanf("%d %d", &n, &qtdeC);
    int casas[n], encomendas[qtdeC];

    for (i = 0; i < n; i++)
    {
        scanf("%d", &casas[i]);
    }
    for (i = 0; i < qtdeC; i++)
    {
        scanf("%d", &encomendas[i]);
    }

    cont = 0;
    loc = 0;
    i = 0;

    while (i < qtdeC)
    {
        if (casas[loc] == encomendas[i])
        {
            i++;
        }
        else if (casas[loc] < encomendas[i])
        {
            loc++;
            cont++;
        }
        else if (casas[loc] > encomendas[i])
        {
            loc--;
            cont++;
        }
    }
    printf("%d", cont);

    return 0;
}

 

[arfneto]

Precisa escolher o campo e classificar. Busca binária só funciona em conjuntos ordenados. A partir daí é só dividir e procurar e dividir...

[Flavio Daniel]

9 minutos atrás, arfneto disse:

Precisa escolher o campo e classificar. Busca binária só funciona em conjuntos ordenados. A partir daí é só dividir e procurar e dividir...

No caso eu estou dando uma pesquisada como eu posso fazer a busca binária mas não estou entendendo muito bem, seria uma função no caso?

[herbertbahia]

39 minutos atrás, Flavio Daniel disse:

seria uma função no caso?

sim é uma função.

geralmente recebe tres parametros um vetor, o argumento e o tamanho .

 

[Flavio Daniel]

1 minuto atrás, herbertbahia disse:

sim é uma função.

geralmente recebe tres parametros um vetor, o argumento e o tamanho .

nao entendir o que seu algoritmo postado tem a ver...

No caso é uma questão do OBI, mas acho que não tenho que usar a busca binária e sim ordenação!
A questão é essa https://olimpiada.ic.unicamp.br/pratique/pu/2014/f1/carteiro/

[herbertbahia]

#include <bits/stdc++.h>

using namespace std;

int max(int a, int b) {
    if (a - b < 0) {
        return b - a;
    }
    return a - b;
}

int main() {
    int n, m, x, count = 0, pos, ini;
    cin>> n>>m;
    vector<int>v;
    vector<int>::iterator it;

    for(int i=0; i< n; i++) {
        cin>> x;
        v.push_back(x);
    }

    ini = 0;
    for(int i=0; i< m; i++) {
        cin>> x;
        if(binary_search(v.begin(), v.end(), x)) {
            it = lower_bound(v.begin(), v.end(), x);
            pos = it - v.begin();

            count+= max(pos, ini);
            ini = pos;
        }
    }

    cout<<count<<endl;
}

 

[Flavio Daniel]

@herbertbahia

No caso isso seria a função em c++? pois estou usando C 

[arfneto]

1 hora atrás, Flavio Daniel disse:

No caso eu estou dando uma pesquisada como eu posso fazer a busca binária mas não estou entendendo muito bem, seria uma função no caso

 

não precisa ser uma função, mas é mais fácil assim
 

31 minutos atrás, Flavio Daniel disse:

@herbertbahia

No caso isso seria a função em c++? pois estou usando C 

 

Não precisa ser uma função. Pode programar isso em qualquer linguagem. É um algoritmo. Divide e vê em que metade está. Aí divide de novo até encontrar... Por isso deve estar ordenado.

 

 

Talvez não devesse postar um link pra eu ou alguém  ir acessar atrás do que é sua dúvida e pudesse apenas postar o enunciado você, aqui mesmo

 

De todo modo, se precisa pesquisar num conjunto de casas ou encomendas e o conjunto for relativamente grande usar sort e busca binária não é uma opção incomum.