C++ Busca Binaria em String.

[Lukas22D]

Gostaria de saber como fazer Busca Binária, sendo a busca uma string dentro de um vetor de registro(struct).

 

Se possível mostrar em forma de codigo.

 

[devair1010]

@Lukas22D    geralmente a busca binária é com números , pois ela se baseia em um modo de procura  mais rápida ,  testando apenas a metade da qtd de elementos no vetor  já ordenado , tanto decrescente ou crescente ,  e em string não tem números para serem ordenados ,  então o que você pode fazer é ordenar as string's pelo tamanho  e então buscar por um números que representa o tamanho da string ,  e você pode ver um exemplo nesse link :

https://pt.wikipedia.org/wiki/Pesquisa_binária

[arfneto]

7 horas atrás, devair1010 disse:

 geralmente a busca binária é com números 

 

Não, não é o caso. A busca binária não é "com números". É com posições em um conjunto ordenado. Um conjunto de qualquer coisa que tenha noção de ordem.

 

7 horas atrás, devair1010 disse:

ela se baseia em um modo de procura  mais rápida ,  testando apenas a metade da qtd de elementos no vetor  já ordenado , tanto decrescente ou crescente

 

Não é o caso também. A busca binária não testa "metade da qtd de elementos". No pior caso testa log2 n do tamanho do vetor.

Ou seja, para um milhão de registros a busca binária faz no máximo 20 buscas e não 500.000

 

7 horas atrás, devair1010 disse:

então o que você pode fazer é ordenar as string's pelo tamanho  e então buscar por um números que representa o tamanho da string

 

Não. Apenas use strcmp() que compara as strings, supondo claro que tenham sido colocadas no vetor pela mesma ordem usada por strcmp().

 

A busca binária só faz sentido em um conjunto ordenado.

 

Exemplo

 

Busca binária em  int x[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18 } por 13

 

São 9 elementos: 0+8/2 = 4

• x[4] = 10
  • 10<13 procura na segunda metade
• (8-4)/2 = 2, 2+4 =6, x[6] = 14
  • 14>13 procura na primeira metade
• (8-6)/2 = 1 + 6 = 7, x[7] = 16
  • 16>13 procura na primeira metade
• (8-7)/2 = 0: fim da linha. Não tem 13....

 

Em casos de busca em um vetor simples como esse de inteiros se para a divisão quando o intervalo fica pequeno, algo como algumas centenas de itens, porque aí é melhor olhar um por um para aproveitar o chache do processador.

 

 

 

Em 08/11/2021 às 23:55, Lukas22D disse:

Gostaria de saber como fazer Busca Binária, sendo a busca uma string dentro de um vetor de registro(struct)

 

Veja o exemplo acima. É a mesma coisa. A busca é por posição num conjunto ordenado, como uma struct que tenha um vetor de strings