Questão 748114

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2012
• Provas: CESGRANRIO - 2012 - Petrobras - Analista de Sistemas Júnior - Engenharia de Software-2012
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Busca; Estrutura de Dados; Vetores

Seja um vetor de inteiros com 400 elementos distintos ordenados em ordem crescente.

Qual é o número máximo de iterações necessárias para encontrar um elemento qualquer do vetor caso seja utilizado o algoritmo de busca binária?

• A. 7
  
• B. 8
  
• C. 9
  
• D. 200
  
• E. 400
  

Gabarito: C

Comentários

• Vamos tentar encontrar 201 entre os 400 itens da lista binária.
  
  Passo 1: Divide 400 por 2 = 200
  Passo 1.1: 201 é maior ou menor que 20? É maior e por isso ficamos com os números entre 200 e 400
  Passo 2: Pega-se o número intermediário entre 200 e 400 = 300
  Passo 2.1: 201 é maior ou menor que que 300? É menor e por isso ficamos com os números entre 200 e 300
  Passo 3: Pega-se o número intermediário entre 200 e 300 = 250
  Passo 3.1: 201 é maior ou menor que 250? É menor e por isso ficamos com os números entre 200 e 250
  Passo 4: Pega-se o número intermediário entre 200 e 250 = 225
  Passo 4.1: 201 é maior ou menor que 225? É menor e por isso ficamos com os números entre 200 e 225
  Passo 5: Pega-se o número intermediário entre 200 e 225 = 213 (arredonda para cima)
  Passo 5.1: 201 é maior ou menor que 213? É menor e por isso ficamos com os números entre 200 e 213
  Passo 6: Pega-se o número intermediário entre 200 e 213 = 207 (arredonda para cima)
  Passo 6.1: 201 é maior ou menor que 207? É menor e por isso ficamos com os números entre 200 e 207
  Passo 7: Pega-se o número intermediário entre 200 e 207 = 204 (arredonda para cima)
  Passo 7.1: 201 é maior ou menor que 204? È menor e por isso ficamos com os núemros entre 200 e 204
  Passo 8: Pega-se o número intermediário entre 200 e 204 = 202
  Passo 8.1: 201 é maior ou menor que 202? É menor e por isso ficamos com os números entre 200 e 202
  Passo 9: Finalmente chega-se no número 201. Veja que foram necessáiros 9 passos de movimento na lista até encontrar o bendito 201.
• O algoritmo de busca binária sempre vai comparar o número procurado com o número que está na posição do meio do vetor. Se o número comparado não for o do meio, caso esse número seja maior número procurado, ele irá jogar fora os números maiores que ele, e caso seja menor que o número procurado, ele joga fora os números menores que ele. O algoritmo repete até que o número procurado seja igual ao número comparado. 
  
  Enquanto (número procurado <> número comparado)
      Lê o número do meio do Vetor
      Se (número comparado > número procurado)
            Vetor novo <- 1ª posição do vetor até o número comparado
      senão
            Vetor novo <- número comparado até a última posição do vetor
   
  Então sua execução: 
  
  1ª iteração pega o do meio (400/2) e compara
  2ª iteração pega o do meio (200/2) e compara
  3ª iteração pega o do meio (100/2) e compara
  4ª iteração pega o do meio (50/2) e compara
  5ª iteração pega o do meio (25/2) e compara
  6ª iteração pega o do meio (12/2) e compara
  7ª iteração pega o do meio (6/2) e compara
  8ª iteração pega o do meio (3/2) e compara
  9ª iteração pega o do meio (1) e compara
   
  
  *Mesmo com um número só, ele ainda vai fazer uma comparação, por isso conta como uma iteração.
• De um modo mais simplório, deve-se lembrar que busca binária é um algoritimo de complexidade O(logN), ou seja, 2^x = 400 2^8 = 256 e 2^9 = 512, assim sendo 8 ainda é menor que o tamanho máximo do vetor e 9 é mais do que suficiente para o mesmo.
• Acho que resolvi esta questão com um pensamento mais simples (no meu ponto de vista).
  
  Em uma busca binária, como os números do vetor estão em ordem (menor para o maior) o algoritmo sempre fará sucessivas divisões por 2 até encontrar o valor desejado. 
  
  Ou seja, pega-se o valor do meio do vetor e, caso não seja o número procurado, verifica-se se o número é maior ou menor e continua-se a busca por uma das duas metades (a metade antes ou a metade depois do valor escolhido no meio do vetor).
  
  Desta forma, no pior caso, para garantir que qualquer número seja encontrado, basta pegar a quantidade de elementos do vetor (400) e ir dividindo o valor por 2, até que se obtenha apenas 1 valor isolado e ir contando as iterações (equivalentes às divisões por 2).
  
  400/2 = 200 (1 iteração)
  200/2 = 100 (2 iterações)
  100/2 = 50   (3 iterações)
  50/2 = 25     (4 iterações)
  25/2 = 13 ( neste caso haverá uma divisão do vetor em 2. Um vetor 12 e outro de 13 elementos.No pior caso, assume-se o maior com 13) (5 iterações).
  13/2 = 7 (idem, com um vetor de 6 e outro de 7 elementos) (6 iterações)
  7/2 = 4 (idem, com um vetor de 3 e outro de 4 elementos) (7 iterações)
  4/2 = 2  (8 iterações)
  2/2 = 1 (9 iterações)
  
  Assim, com essas 9 iterações, encontra-se qualquer elemento em um vetor ordenado de 400 elementos. 

• Fabio a complexidade da busca binária não seria O(log2N)?

• Força Guerreiro!!!!!!