Return of a binary search

Asked

Viewed 871 times

0

I have the following question:

Develop a recursive function that finds a value in an ordered vector using binary search. The function must respond to the position of the vector value. 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 solve this problem?

c

  • Post code as text even to make it easier for people to help.

  • Read this: http://meta.pt.stackoverflow.com/q/5149/132

  • Remember that in C arrays start at position 0, not position 1.

  • Ah, website formatting recognizes lines starting from 4 spaces as source code. So put 4 spaces at the beginning of each line of your code and post. Another alternative is to post your entire code, select it and then click the button {} that appears in your edit bar.

1 answer

2

Your code has several problems.

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

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

In the main, you are iterating and accessing the positions of the array from 1 to tam. It turns out that in C the first element is at position 0, and therefore the last is at position tam - 1.

Ah, and please, for God’s sake, don’t post code in image format. Everyone in this community hates it very much. Code as image is difficult because you can’t copy and paste and change to be able to formulate a response. I, for example, had to take the trouble to write your entire code before posting this answer, work that few people willing to answer would subject themselves to having.

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.

Browser other questions tagged c

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