Implementação de Busca Binária e Funções Relacionadas em C++

Problema I binarysearch Dado um vector int de tamanho T escreva um programa em C que verifique se um determinado número N se encontra nesse vector Quais problemas 2 include iostream include vector include algorithm using namespace std int main vectorint v int i j fori0 i 5 i cin j vpushbackj stablesort vbegin vend cin j if binarysearchvbegin vend j cout Numero encontrado return 0 Problema II lowerbound upperbound include iostream include algorithm lowerbound upperbound sort include vector vector using namespace std int main vectorint meuVector meuVector 8010605040307020 sort meuVectorbegin meuVectorend 1020304050607080 vectorintiterator lowup retorna o iterator para o primeiro elemento que seja maior ou igual a lowlowerbound meuVectorbegin meuVectorend 10 retorna o iterator para o primeiro elemento que seja maior a up upperbound meuVectorbegin meuVectorend 10 cout lowerbound na posição low meuVectorbegin endl cout upperbound na posição up meuVectorbegin endl return 0 Dado um vector int de tamanho T escreva um programa em C retorne 1º elemento que seja maior ou igual a um valor N qualquer 1º elemento que seja maior do que um valor N qualquer Quais problemas Problema III busca binária Dado um determinado vector de inteiros com tamanho T escreva um programa em C que contenha uma função de busca binária a qual retorna 1 quando o elemento não for encontrado no vector ou Caso o elemento exista no vector retorne sua posição 4 Problema III busca binária esquerda direita meio esquerda direita esquerda2 N vetormeio 0 14 0 14 0 2 7 53 25 meio 1 8 14 8 148 2 11 53 49 Meio 1 12 14 12 1412 2 13 53 53 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 5 8 12 33 21 22 25 31 44 46 49 51 53 55 8 9 10 11 12 13 14 31 44 46 49 51 53 55 12 13 14 51 53 55 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 5 8 12 33 21 22 25 31 44 46 49 51 53 55 8 9 10 11 12 13 14 31 44 46 49 51 53 55 12 13 14 51 53 55 Problema III busca binária esquerda direita meio esquerda direita esquerda2 N vetormeio 0 14 0 14 0 2 7 44 25 meio 1 8 14 8 148 2 11 44 49 8 meio 1 10 8 10 82 9 44 44 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 5 8 12 33 21 22 25 31 44 46 49 51 53 55 8 9 10 11 12 13 14 31 44 46 49 51 53 55 8 9 10 31 44 46 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 5 8 12 33 21 22 25 31 44 46 49 51 53 55 8 9 10 11 12 13 14 31 44 46 49 51 53 55 8 9 10 21 44 46 Busca Binária include iostream include vector include string include algorithm using namespace std int buscaBinariavectorint vetor int valorProcurado int esquerda 0 int direita vetorsize 1 while esquerda direita int meio esquerda direita esquerda 2 if vetormeio valorProcurado return meio if vetormeio valorProcurado O valor está à direita do meio esquerda meio 1 else O valor está à esquerda do meio direita meio 1 return 1 O valor não foi encontrado int mainvoid int n 5 a vectorint vTeste cout Informe os elementos do Vector int numero forint i0ini cin numero vTestepushbacknumero sortvTestebegin vTesteend cout endl cout Informe o número a ser procurado cin a cout endl int indice buscaBinariavTeste a if indice 1 cout O elemento não foi encontrado else cout O elemento foi encontrado return 0 Busca Binária Quais as vantagens Complexidade Θlog2 n 8