Return of a binary search

Question

Return of a binary search

Navigation

#1 by (1 votes)

0

I have the following question:

Develop a recursive function that finds a value in an ordered vector using binary search. The function must give the position of the vector value as a response. If the value is not in the vector, it returns -1.

Then I developed the following:

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

int BuscaBinaria(int[] v, int inicio, int fim, int valor) {
    int meio;
    meio=(inicio+fim)/2;
    if(meio>valor)
    {
        return BuscaBinaria(v, inicio, meio-1, valor);
    }
    if(meio<valor)
    {
        return BuscaBinaria(v, inicio+1, meio, valor);
    }
    if(meio==valor)
    {
        return meio;
    }
    else {
    return -1;
    }
}
int main()
{
    int tam, valor;
    int k;
    printf("Qual o tamanho do vetor: ");
    scanf("%d", &tam);
    int v[tam], i;
    printf("Informe os valores do vetor:\n");
    for(i=1; i<=tam; i++)
    {
        scanf("%d", &v[i]);
    }
    printf("Informe o numero a ser buscado: ");
    scanf("%d", &valor);
    k= BuscaBinaria(v,1,tam,valor);
    printf("%d", k);
}

But when the value is not inside the vector, the program gives error. It stops and returns any number at the end. How can I resolve this problem?

c

asked by anonymous 22.11.2016 / 16:01

1 answer

Make this grid with Flexbox JavaScript event if it is repeated in other IDs

score 1 · Answer 1

Your code has several problems.

First you make checks such as (meio>valor) instead of (v[meio]>valor) . This is important because if you notice well, at no time of your binary search you are accessing the elements of the array, so it would not work.

In addition, the criterion in which it returns -1 is when fim is equal to inicio without the searched element being in that position. As you put it, it would never return -1, since whatever the values of meio and valor , there is no way that all conditions meio>valor , meio<valor and meio==valor are all false to same time.

In main , you are iterating and accessing array positions from 1 to tam . It occurs that in C the first element is in position 0, so the latter is in position tam - 1 .

Oh, and please, for God's sake, do not post code in image format. Everyone in this community hates it very much. Code as image is difficult because you can not copy and paste and leave changing to be able to formulate a response. I for example had to bother to retype your entire code before posting this answer, a job that few people willing to answer would have to have.

With all these changes, your code looks like this:

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

int BuscaBinaria(int v[], int inicio, int fim, int valor) {
    int meio = (inicio + fim) / 2;
    if (v[meio] == valor) return meio;
    if (fim == inicio) return -1;
    if (v[meio] > valor) return BuscaBinaria(v, inicio, meio - 1, valor);
    return BuscaBinaria(v, inicio + 1, meio, valor);
}

int main() {
    int tam, valor;
    printf("Qual o tamanho do vetor: ");
    scanf("%d", &tam);
    int v[tam], i;
    printf("Informe os valores do vetor:\n");
    for (i = 0; i < tam; i++) {
        scanf("%d", &v[i]);
    }
    printf("Informe o numero a ser buscado: ");
    scanf("%d", &valor);
    int k = BuscaBinaria(v, 0, tam - 1, valor);
    printf("%d", k);
}

See here working on ideone.