Questão de TI - Desenvolvimento de Sistemas — Métodos de Busca — CESGRANRIO 2021
TI - Desenvolvimento de SistemasMétodos de Busca
- Código
- cg056187
- Banca
- CESGRANRIO
- Órgão
- BB
- Ano
- 2021
- Cargo
- Esc
O gerente de uma agência bancária recebe, diariamente, solicitações de seus clientes com dúvidas sobre a melhor decisão para aplicações financeiras e as armazena, com um código numérico crescente, num vetor de solicitações, para respondê-las ao final do expediente. Para manter o conceito de bom atendimento, o gerente gostaria, sempre que possível, que a ordem das respostas seguisse, estritamente, a ordem de chegada das solicitações. Entretanto, há casos em que é necessário, por motivos de emergência ou por prioridade legal, localizar determinado código numérico para atender à solicitação correspondente antes das demais, “furando” a fila de espera. O gerente solicitou, então, à equipe de TI do banco, uma proposta que conciliasse essas duas necessidades. Ao estudar o problema, a equipe de TI concluiu que uma solução que mapearia diretamente essa necessidade da gerência seria permitir a realização de uma busca binária sobre o vetor de solicitações ordenado pelos seus códigos numéricos. Verificando a viabilidade dessa sugestão, o grupo de TI calculou que, se considerar a existência de N solicitações, a quantidade de iterações necessárias para localizar determinado código numérico no vetor de solicitações, utilizando a busca binária, no pior caso, é
- A\left \lfloor log_2 N \right \rfloor , em que a notação \left \lfloor x \right \rfloor significa maior inteiro menor ou igual a x.
- B1 + \left \lfloor log_2 N \right \rfloor, em que a notação \left \lfloor x \right \rfloor significa maior inteiro menor ou igual a x.
- C1 + \left \lfloor log_2 N \right \rfloor, em que a notação \left \lfloor x \right \rfloor significa menor inteiro maior ou igual a x.
- D2N.
- E2N-1