Algoritmo: 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.

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 {

/ **

* /

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;

}

}

Tagged