Blog sobre Algoritmos, Estruturas de Dados, Códigos, Plataformas Java e Móvel
Compartilhando um pouco, eu sei
HomeAbout
«Implementar uma função de raiz quadrada de inteiro rápido que obtém um inteiro não assinado de 32 bits e retorna outro inteiro não assinado de 32 bits que é o piso do raiz quadrada da entrada. Suponha que, além de serem classificadas, as entradas de A sejam inteiros distintos. Projete um algoritmo eficiente para encontrar um índice i tal que A [i] = i ou indicando que não existe tal índice »
Escreva um método que pegue um array ordenado A de inteiros e uma chave ke retorne o índice da primeira ocorrência de k em A. Retorne -1 se k não aparecer em A.
public class FindFirstOccurrenceBinarySearch {
/ **
- @param args
* /
public static void main (String [] args) {
int [] input = {1,1,1,1,2,2,2,3,3,3,3,3,3,3,4,4,4,4};
chave int = 2;
System.out.println (“A primeira ocorrência da chave:” + chave + ”é em:” + getFirstOccurrence (input, key));
}
private static int getFirstOccurrence (int [] input, int key) {
int baixo = 0;
int alto = input.length-1;
int mid = 0;
int indexFound = -1;
enquanto (baixo <= alto)
{
médio = baixo + (alto – baixo) / 2;
if (key == input [mid])
{
indexFound = mid;
quebrar;
}
else if (key> input [mid])
{
baixo = médio + 1;
}
outro
{
alto = médio -1;
}
}
if (indexFound! = -1)
{
System.out.println (indexFound);
// a primeira ocorrência deve ser entre o início da matriz e indexFound
baixo = 0;
alto = indexFound;
enquanto (baixo <= alto)
{
médio = baixo + (alto-baixo) / 2;
System.out.println (baixo + ”:” + alto + ”:” + médio);
if (tecla! = entrada [mid])
{
baixo = médio + 1;
}
outro
{
indexFound = mid;
alto = médio – 1;
}
}
}
return indexFound;
}
}