Busca Binária

[rhyu 0]

Preciso resolver esse exercício, mas estou com problemas.

 

Exercicio: Faça uma função de busca binária com o seguinte protótipo:

void busca (int vet [ ] , int tam, int chave, int posicoes [ ] ,int *n)

O vetor posições deve devolver as posições do vetor em que a chave ocorre, e em *n o número de ocorrências dessa chave.

O que eu fiz mas, ta dando problema de segmentação

 

 

/*Busca Binaria*/
#include <stdio.h>
#include <stdlib.h>
#define TAM 30
void ordena(int vet[], int tam)
{
    int i, j, aux;
    for (i = tam - 1; i >= 1; i--) {
        for (j = 0; j < i; j++) {
            if (vet[j] > vet[j + 1]) {
                aux = vet[j];
                vet[j] = vet[j + 1];
                vet[j + 1] = aux;
            }
        }
    }
}
void busca(int vet[], int tam, int chave, int posicoes[], int *n)
{
    int direita=tam-1, esquerda=0, meio, k = 0, cont = 0;
    while (esquerda <= direita) {
        meio = (direita + esquerda) / 2;
        if (vet[meio] == chave) {
            posicoes[k] = meio;
            cont++;
            k++;
        } else if (chave < vet[meio])
            direita = meio - 1;
        else
            esquerda = meio + 1;
    }
    *n = cont;
}

int main()
{
    int i, vet[TAM], posicoes[TAM], tam, *n, chave;
    n = vet;
    scanf("%d %d", &tam, &chave);
    for (i = 0; i < tam; i++) {
        scanf("%d", &vet[i]);
    }
    ordena(vet, tam);
    busca(vet, tam, chave, posicoes, n);
    printf("A chave %d aparece %d vezes, nas posicoes ", chave, *n);
    for (i = 0; i<*n; i++)
        printf("%d ", posicoes[i]);
    return 0;
}

 

Estive a pesquisar a respeito desse erro de Falha de Segmentação, e achei sobre gdb, fiz alguns procedimentos e tive isso

backstrace
Program received signal SIGSEGV, Segmentation fault.
0x00000000004005f0 in ordena (vet=0x7fffffffe0c0, tam=32767) at ex1v2.c:11
11             if (vet[j] > vet[j + 1]) {

Um problema na função ordena? Em outro exercício usei a mesma função e não ocorreu nenhum problema

[F.Ramon 1]

mano em Geral erro de Segmento ocorrem algum segmento de memória é sobrescrito, no seu código está havendo transbordamento, certamente por que o array vet está recebendo mais dados do que ele suporta.no C++ temos os alocadores dinâmicos,no C creio que terá que passar a função free.boa sorte,espero ter ajudado

[]' abs

[ScreenBlack 13]

Está apontando a variável "n" para um vetor, mas definindo ela sem especificar a posição. Logo, todo valor atribuído a ela, será armazenado na primeira posição.

 

Compilei seu código aqui, usando MinGW e GCC, porém, nenhum deles mostrou esse erro quando informei uma quantidade de valores inferiores ao máximo.

Não seria por estar informando mais valores que o permitido em "#define TAM 30"?

 

Outro erro, está na última função "for()" da função "main()". O loop vai até o valor contido na primeira posição do vetor e que está vindo errado.

Pra evitar problema desse tipo, use a própria variável "tam" como limite máximo do loop.

 

Segue a saída da execução do código (adicionei um debug para validar os valores dos vetores "vet" e "posicoes"), compilado pelo GCC:

$ ./Busca
5 1
5
4
3
2
1
vetor: 1
vetor: 2
vetor: 3
vetor: 4
vetor: 5
posicoes: 0
posicoes: 0
posicoes: 0
posicoes: 0
posicoes: 0
A chave 1 aparece 31 vezes, nas posicoes 0 0 0 0 0