Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca)

Como usar a busca binária em C - Pesquisa binária na linguagem C

Quantidade de visualizações: 476 vezes
A busca binária, ou pesquisa binária, é um algoritmo eficiente para encontrar um item em uma lista (vetor ou array) ordenada. Sim, os itens devem, obrigatoriamente, estar ordenados.

O processo é bem simples. A busca binária começa a partir do meio da lista e compara o item nesta posição com o valor sendo pesquisado. Se o valor não for encontrado e for menor que o item no meio da lista, o algoritmo passa para a porção à esquerda da lista, eliminando, assim, metade dos elementos do vetor ou array (a porção maior que o valor pesquisado).

Se o valor não for encontrado e for maior que o item no meio da lista, então a busca reinicia a partir da metade da sub-lista à direita (os itens maiores que o valor pesquisado). Essa divisão continua até que o valor seja encontrado ou não seja mais possível dividir a lista pela metade.

Se um array ou vetor possuir 100 elementos e usarmos a busca binária nele, precisaremos efetuar no máximo 7 tentativas para encontrar o valor desejado. Se a lista possuir 4 bilhões de itens nós teremos que fazer no máximo 32 tentativas.

Isso acontece porque a pesquisa binária é executada em tempo logarítmico, ou seja, log2 n, onde n é a quantidade de itens no vetor. Dessa forma, se tivemos 1.000 itens em um array, log2 1000 = 10 tentativas. Lembre-se de que, na programação log e log2 retornam resultados diferentes: log(10) = 2.302585092994046 enquanto log2(10) = 3.321928094887362. Na análise da busca binária nós usamos sempre log2.

Vamos agora ver como podemos codificar a busca binária em C. Veja o código a seguir:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

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

#define TAM_ARRAY 10

// função principal do programa
int main(int argc, char *argv[]){
  setlocale(LC_ALL,""); // para acentos do português
  
  // variáveis para ajudar na resolução do problema
  int i, numero, esquerda, direita, meio, encontrado;
  
  // vamos criar uma um vetor ordenado de inteiros
  int valores[] = {3, 5, 7, 8, 9, 12, 43, 50, 52, 60};
  
  // vamos mostrar os elementos do vetor
  printf("Os valores do array são: ");
  for(i = 0; i < TAM_ARRAY; i++){
    printf("%d, ", valores[i]);
  }
  
  // vamos pedir o item a ser pesquisado
  printf("\n\nInforme o número a ser pesquisado: ");
  scanf("%d", &numero);

  // agora vamos pesquisar o número no array usando a pesquisa
  // binária
  // a variável esquerda aponta para o primeiro elemento do vetor
  esquerda = 0;
  // a variável direita aponta para o último elemento do vetor
  direita = TAM_ARRAY - 1;
  // para indicar se o valor foi encontrado
  encontrado = 0;

  // enquanto houver mais de um elemento a ser comparado
  while (esquerda <= direita){
    // obtemos o elemento na metade da lista
    meio = (esquerda + direita) / 2;
    
    // fazemos a comparação
    if (numero == valores[meio]){
      printf("O número foi encontrado no índice %d", meio);
      encontrado = 1;  
      break; // sai do laço
    }
        
    // o item atual é maior que o valor pesquisado?
    if (valores[meio] > numero){
      direita = meio - 1;
    }  
    // o item atual é menor que o valor pesquisado?
    else{
      esquerda = meio + 1;
    }
  }
    
  // o valor foi encontrado?
  if (!encontrado){
    printf("O valor pesquisado não foi encontrado");  
  }
  
  printf("\n\n");
  system("PAUSE");
  return 0;
}

Ao executar este código C nós teremos o seguinte resultado:

Os valores da lista são: [3, 5, 7, 8, 9, 12, 43, 50, 52, 60]
Informe o número a ser pesquisado: 9
O número foi encontrado no índice 4

Link para compartilhar na Internet ou com seus amigos:

C ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Exercícios Resolvidos de C - Escreva um programa C para mover todos os zeros para o final do vetor, sem alterar a ordem dos elementos já presentes no array

Quantidade de visualizações: 731 vezes
Pergunta/Tarefa:

Dado o seguinte vetor de inteiros:

// vamos declarar e construir um vetor de 8 inteiros
int valores[] = {0, 3, 0, 5, 7, 4, 0, 9};
Escreva um programa C para mover todos os zeros para o final do vetor, ou seja, para a direita, sem alterar a ordem dos elementos diferentes de zero já presentes no array e sem criar um vetor adicional ou temporário.

Sua saída deverá ser parecida com:

Vetor na ordem original:

0   3   0   5   7   4   0   9   

Vetor com os zeros deslocados para o final:

3   5   7   4   9   0   0   0
Resposta/Solução:

Veja a resolução comentada deste exercício usando C:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
  
int main(int argc, char *argv[]){
  // vamos declarar e construir um vetor de 8 inteiros
  int valores[] = {0, 3, 0, 5, 7, 4, 0, 9};
  int i; // para o controle do laço
  int j; // variável auxiliar
  int temp; // variável temporária
  
  setlocale(LC_ALL,""); // para acentos do português
		
  // vamos mostrar o vetor na ordem original
  printf("Vetor na ordem original:\n");
  for(i = 0; i < 8; i++){
    printf("%d   ", valores[i]);
  }
    
  // vamos inicializar j como 0 para que ele aponte para
  // o primeiro elemento do vetor
  j = 0;
    
  // agora o laço for percorre todos os elementos do vetor,
  // incrementanto a variável i e deixando o j em 0
  for(i = 0; i < 8; i++){
    // encontramos um valor que não é 0
    if(valores[i] != 0){
      // fazemos a troca entre os elementos nos índices
      // i e j
      temp = valores[i];
      valores[i] = valores[j];
      valores[j] = temp;
      // e avançamos o j para o elemento seguinte
      j++;
    }
  }
    
  // agora mostramos o resultado
  printf("\n\nVetor com os zeros deslocados para o final:\n");
  for(i = 0; i < 8; i++){
    printf("%d   ", valores[i]);
  }
    
  printf("\n\n");
  system("pause");
  return 0;
}

Não se esqueça: A resolução do exercício deve ser feita sem a criação de um vetor, array ou lista adicional, e os elementos diferentes de zero devem permanecer na mesma ordem que eles estavam antes.


C ::: Dicas & Truques ::: Recursão (Recursividade)

Como somar os elementos de um vetor em C usando uma função recursiva - Linguagem C para iniciantes

Quantidade de visualizações: 5251 vezes
Em algumas ocasiões ficamos imaginando o que pode ser feito com os métodos e funções recursivas. A resposta é: praticamente tudo.

Veja abaixo um programa C completo no qual eu mostro como escrever uma função recursiva que recebe um array e mostra a soma de seus elementos (lembre-se de que um array é o mesmo que vetor, ou seja, uma matriz de uma linha e várias colunas):

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

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

// função recursiva para somar todos os elementos de um array
int somar(int indice, int tamanho, int vetor[]){
  // o caso base...hora de encerrar a recursividade
  if(indice == (tamanho - 1)){
    return vetor[indice];
  }
  else{
    // ainda não é o caso base? vamos fazer uma nova chamada à função somar()
    return vetor[indice] + somar(indice + 1, 10, vetor);
  }
}

// função principal do programa
int main(int argc, char *argv[]){
  // vamos declarar um array de 10 elementos
  int valores[10];
  int i, soma;

  // vamos pedir ao usuário para informar os valores para o vetor
  for(i = 0; i < 10; i++){
    printf("Informe o valor do elemento %d: ", i);
    scanf("%d", &valores[i]); 
  }

  // vamos efetuar uma chamada à função recursiva somar();
  // nota que estamos passando o índice inicial, o tamanho do
  // array e o array em si
  soma = somar(0, 10, valores);
  printf("\nA soma dos elementos è: %d", soma);
  
  printf("\n\n");
  system("PAUSE");
  return 0;
}

Ao executarmos este código C nós teremos o seguinte resultado:

Informe o valor do elemento 0: 7
Informe o valor do elemento 1: 3
Informe o valor do elemento 2: 1
Informe o valor do elemento 3: 3
Informe o valor do elemento 4: 8
Informe o valor do elemento 5: 9
Informe o valor do elemento 6: 4
Informe o valor do elemento 7: 3
Informe o valor do elemento 8: 2
Informe o valor do elemento 9: 6

A soma dos elementos é: 46


C ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Exercícios Resolvidos de C - Desafio do número ausente. Dado um vetor de números naturais 1..n, encontre o valor ausente

Quantidade de visualizações: 550 vezes
Pergunta/Tarefa:

Dado o vetor:

int valores[] = {1, 8, 7, 2, 6, 5, 3};


Encontre o elemento ausente na sequência de valores do vetor, sabendo que o primeiro valor é 1 e o último elemento é 8. Perceba que o vetor não precisa estar ordenado. Além disso, o entrevistador se certificará de que os valores serão sempre positivos e não haverá valores repetidos.

Sua saída deverá ser parecida com:

O número ausente é: 4
Resposta/Solução:

Dica: Use a fórmula n * (n + 1) / 2 para facilitar a resolução do exercício.

Veja a resolução comentada deste exercício usando C:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

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

// função principal do programa
int main(int argc, char *argv[]){
  // vamos declarar um vetor de inteiros faltando
  // um valor na sequência (não necessariamente ordenada)
  // Note a ausência do número 4
  int valores[] = {1, 8, 7, 2, 6, 5, 3};
  int i, soma_n, ausente, soma_elementos;
  int quant = 8; // tamanho do vetor + 1
	
  setlocale(LC_ALL,""); // para acentos do português 
  
  // o primeiro passo é obter a soma de 1..n elementos
  // natuais usando a fórmula n*(n+1)/2
  soma_n = (quant * (quant + 1)) / 2;
    
  // agora vamos somar os elementos do vetor
  soma_elementos = 0;
  for(i = 0; i < 7; i++){
    soma_elementos = soma_elementos + valores[i];
  }
    
  // agora calculamos o valor ausente
  ausente = soma_n - soma_elementos;
    
  // vamos mostrar o resultado
  printf("O número ausente é: %d", ausente);
  
  printf("\n\n");
  system("PAUSE");	
  return 0;
}



Vamos testar seus conhecimentos em Fenômeno de Transportes e Hidráulica

Fórmula de Hazen-Williams

A fórmula de Hazen-Williams (1903) é resultado de um estudo estatístico com grande número de dados experimentais, recomendada para escoamento turbulento de transição, água a 20ºC e diâmetro maior ou igual a 50mm.

Calcule o diâmetro de uma tubulação de aço (C=90), com 1.000m de comprimento e perda de carga de 51m, cuja vazão é de 200l/s.

A) Aproximadamente 0,3m de diâmetro.

B) Aproximadamente 0,4m de diâmetro.

C) Aproximadamente 0,1m de diâmetro.

D) Aproximadamente 0,5m de diâmetro.

E) Aproximadamente 0,2m de diâmetro.
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Hidrologia

Marque a alternativa que indica uma característica da rede hidrográfica brasileira.

A) É formada principalmente por rios intermitentes.

B) Não apresenta cursos de água em área de planalto.

C) Possui rios com o predomínio de foz do tipo estuário.

D) Todos os rios brasileiros possuem regime nival.

E) É composta por rios de baixo aproveitamento hídrico.
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em JavaScript

Na construção switch...case...default do JavaScript, em qual parte colocamos a expressão a ser avaliada?

A) O JavaScript não possui switch...case

B) switch

C) case

D) default
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em JavaScript

Qual o resultado da execução do seguinte código JavaScript?

document.write(false == '0');

A) 0

B) false

C) 1

D) true

E) Erro de execução
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Engenharia Civil - Estruturas de Aço e Madeira

Evolução das estruturas

Até o início do século XIX os metais exerciam uma função estrutural limitada nas edificações. O aço em abundância e econômico tornou-se disponível pela primeira vez na década de 1850. Assinale a opção correta quanto aos motivos que levaram à expansão da utilização de elementos metálicos em estruturas:

Selecione a resposta:

A) A utilização do ferro forjado e o sentido estético da época levaram a maior utilização da estrutura metálica.

B) Devido à introdução do Processo Bessemer, em que grandes quantidades de ferro podiam ser transformadas em aço, em aproximadamente 20 minutos resultando em um metal com propriedades estruturais bastante superiores ao do ferro fundido.

C) A carência de profissionais capacitados, artesãos, em trabalhar a alvenaria de pedra como elemento estrutural levaram a uma mudança em termos de tecnologia estrutural, havendo a utilização da estrutura metálica em larga escala.

D) O incremento da urbanização e a necessidade da rapidez na construção de casas para as pessoas que vinham para as cidades trabalhar nas fábricas levaram à larga utilização da estrutura metálica, reduzindo assim, o seu custo.

E) A verticalização das cidades e a ousadia dos arquitetos e dos construtores de se construir edifícios cada vez mais altos.
Verificar Resposta Estudar Cards Todas as Questões

Mais Desafios de Programação e Exercícios e Algoritmos Resolvidos de C

Veja mais Dicas e truques de C

Dicas e truques de outras linguagens

Códigos Fonte

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento
Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesControle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades
Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: Delphi
6º lugar: C
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2024 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 30 usuários muito felizes estudando em nosso site.