Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/08/16
003// 
004// Descricao: funcao "buscaBinaria(int vet[], int e, int d, int x)"
005// 1. Devolve i se x ocorre entre as posicoes e e d, -1 em caso contrario
006// 2. Dados programa principal que
007//    * entrada dados: dados no codigo, pois tem que estar ordenado!
008//    * buscas:        usando a funcao de 1, o usuario devera digitar um valor, se negativo pare (e nada imprime), senao
009//                     verifique se valor no vetor (imprimindo sua posicao ou -1 se nao estiver no vetor)
010//                     o programa para quando usuario digitar um valor negativo (neste caso o programa deve imprimir NADA).
011
012#include <stdio.h>
013
014#define MAX 50
015
016// Ideia: pega elemento do meio, se menor que x busca na metade direita, se maior, busca na metade esquerda
017// Complexidade: O(log n) pois a cada passo elimina metade dos elementos
018// Param:   'vet[]' vetor com dados, 'int e' indice esquerdo, 'int d' indice direito, 'int x' elemento buscado
019// Devolve: j entre e e d se encontrou na posicao j; -1 se x nao pertence a 'vet[e..d]'
020int buscaBinaria (int vet[], int e, int d, int x) {
021  int m;
022  while (e <= d) {   // invariante: 'x' NAO pertence a 'vet[0..e-1]' e nem a 'vet[d+1..n-1]'
023    m = (e + d) / 2; // media (lembre-se: divisao inteira)
024    if (vet[m]<x) // metade esquerda NAO contem x
025      e = m+1;
026    else
027    if (vet[m]>x) // metade direita NAO contem x
028      d = m-1;
029    else
030      return m; // encontrou!
031    }
032  return -1;
033  }
034
035int main (void) {
036  int n = 9, vet[] = { 0, 2, 2, 3, 5, 6, 7, 7, 9 }; // tem que estar ordenado...
037  int i, x = 0;
038  // entrada de dados: tem que estar ordenado!
039  //D scanf("%d", &n); for (i=0; i<n; i++) scanf("%d", &vet[i]);
040  for (i=0; i<n; i++) printf("%d ", vet[i]);
041  printf("\nBuscas...\n");
042  // buscar elementos (digitar negativo finaliza programa)
043  x = 0;
044  while (x>=0) {
045    scanf("%d", &x);
046    if (x>=0) {
047      i = buscaBinaria(vet, 0, n, x);
048      if (i>=0)
049         printf("* achei %d em vet[%d]\n", x, i);
050      else
051         printf("* %d nao esta no vetor!\n", x); // NAO encontrado
052      }
053    }
054  return 0;
055  }