Algoritmo: 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 tal índice não existe

public class SearchForIndexEqualToDataBinarySearch {

public static void main (String [] args)

{

/ **

  • Problema: PESQUISAR UMA MATRIZ CLASSIFICADA PARA A [i] = i. Todos os inteiros são distintos

*

  • Solução: Faça uma pesquisa binária, se A [mid]> mid nenhum elemento à direita do mid pode atender a este critério.

  • Se A [mid] <mid, então o elemento a ser pesquisado está no lado direito do mid na matriz.

* /

int [] input = {-5, -3,2,3,5,10,12,14,16};

findTheIndexWithDataEqualToIndex (input);

}

private static void findTheIndexWithDataEqualToIndex (int [] input) {

int baixo = 0;

int alto = comprimento de entrada – 1;

int mid = 0;

enquanto (baixo <= alto)

{

médio = baixo + (alto – baixo) / 2;

if (input [mid] == (mid + 1))

{

System.out.println (“O índice e o valor são:“ + input [mid]);

quebrar;

}

else if (input [mid]> (mid + 1))

{

alto = médio – 1;

}

outro

{

baixo = médio + 1;

}

}

}

}

Tagged