Pesquisa binária para encontrar o intervalo em que o número está
Eu tenho um array
Values array: 12 20 32 40 52
^ ^ ^ ^ ^
0 1 2 3 4
em que eu tenho que executar pesquisa binária para encontrar o índice do intervalo em que o número se encontra. Por exemplo:
Dado o número -> 19 (fica entre o índice 0 e 1), retorne 0Dado o número -> 22 (situa-se entre os índices 1 e 2), retorne 1Dado o número -> 40 (situa-se entre os índices 3 e 4), retorne 3Eu implementei a pesquisa binária da seguinte maneira, e isso está correto para o caso 1 e 3, mas incorreto se procurarmos pelo caso 2 ou 52, 55 32, etc.
#include <iostream>
using namespace std;
int findIndex(int values[], int number, unsigned first, unsigned last)
{
unsigned midPoint;
while(first<last)
{
unsigned midPoint = (first+last)/2;
if (number <= values[midPoint])
last = midPoint -1;
else if (number > values[midPoint])
first = midPoint + 1;
}
return midPoint;
}
int main()
{
int a[] = {12, 20, 32, 40, 52};
unsigned i = findIndex(a, 55, 0, 4);
cout << i;
}
Uso de variáveis adicionais, comobool found
não é permitido.