Este artigo compartilha com você a variante do Java Implementando a pesquisa binária de referência. O conteúdo específico é o seguinte
Pesquisa binária normal:
Primeiro revise a pesquisa binária comum
Nota: Há um problema com a pesquisa binária: quando há duplicações na matriz, como {3, 3, 3, 3}, quando a pesquisa binária 3, o retorno é arr [1], o que significa que a pesquisa binária não retornará a posição 0 da primeira ocorrência de 3.
classe pública bininaresearch {public static <t estende comparável <?? super t >> int search (t arr [], valor t) {int left = 0; int correto = arr.length - 1; while (esquerda <= direita) {int mid = (esquerda e direita) + ((esquerda ^ direita) >> 1); if (arr [mid] .compareto (value) == 0) {return mid; } else if (arr [mid] .compareto (valor)> 0) {direita = mid - 1; } else {esquerda = MID + 1; }} retornar -1; } public static void main (string [] args) {integer [] arr = new Integer [] {1, 3, 3, 6, 7, 9}; //-1 System.out.println (pesquisa (arr, 0)); // 0 system.out.println (pesquisa (arr, 1)); // 5 system.out.println (pesquisa (arr, 9)); //-1 System.out.println (pesquisa (arr, 10)); // 2 system.out.println (pesquisa (arr, 3)); }}Variante bipartida: Findfirst Função
Na pesquisa binária normal, pesquise no intervalo [esquerda ...... direita] fechado à esquerda e fechado à direita. Se um elemento com um valor for encontrado, ele será considerado para ser encontrado. Este não é o caso nesta função Findfirst. No intervalo [esquerdo ...... direita] fechado à esquerda, quando o elemento com um valor é igual ao valor é encontrado, em vez da direita = MID-1, deixe à direita = MID, continue pesquisando no intervalo [esquerdo ...... direita] fechado à esquerda. O loop sai quando esquerda == Finalmente sai.
Depois de sair do loop, o valor pode ser encontrado, ou pode ser que o loop não encontre o valor depois de atravessar a matriz completa e sair do loop.
Então, depois de sair do loop, você deve julgar qual situação é.
classe pública bininaresearch {public static <t estende comparável <?? super t >> int findfirst (t arr [], valor t) {int esquerd = 0; int correto = arr.length - 1; // Sair quando esquerda> = à direita, a situação "=" aqui é diferente de binária enquanto (esquerda <direita) {int mid = (esquerda + direita) >> 1; if (arr [mid] .compareto (valor) <0) {esquerda = mid + 1; } else {Right = MID; }} // Após o loop acima ser percorrido. O valor foi encontrado? Ainda não foi encontrado nenhum valor? Apenas faça um julgamento. if (arr [esquerda] == valor) {return à esquerda; } else {return -1; }} public static void main (string [] args) {Integer [] arr = new Integer [] {1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9, 9}; //-1 system.out.println (findfirst (arr, 0)); // 0 system.out.println (findfirst (arr, 1)); // 12 system.out.println (findfirst (arr, 9)); //-1 system.out.println (findfirst (arr, 10)); // 1 system.out.println (findfirst (arr, 3)); }}Variante bipartida: menos função
introduzir
Dada uma matriz e um valor variável, encontre o número da matriz mais próxima do valor do valor e menor que o valor. Por exemplo, arr = {11, 22, 22, 33, 33, 33, 44, 54} valor = 33. 22 é o mais próximo do valor e menor que o valor.
Portanto, a resposta é 2 (22 no marcador do canto inferior na Array Arr).
Se nenhum número menor que o valor for encontrado, a saída -1.
Solução
Use o método de pesquisa binária. Cada vez, use arr [mid] para comparar com o valor. Pequeno, igual, vá para a esquerda para procurá -lo; Grande, vá para a direita para procurá -lo. Você pode não entender a situação "igual" na frase anterior. A pesquisa binária comum é encontrar o ARR [MID] == Valor, enquanto menor a função é encontrar um número menor que o valor; portanto, embora arr [mid] == valor, você deve continuar procurando um valor menor à esquerda.
exemplo
Código
classe pública bininaresearch {public static <t estende comparável <?? super t >> int menos (t arr [], valor t) {int esquerd = 0; int correto = arr.length - 1; // Sair enquanto quando esquerda> direita (esquerda <= direita) {int mid = (esquerda e direita) + ((esquerda ^ direita) >> 1); if (value.compareto (arr [mid]) <= 0) {direita = mid - 1; } else {esquerda = MID + 1; }} retornar à direita; } public static void main (string [] args) {integer [] arrf = new Integer [] {21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; // 3 System.out.println (menos (ARRF, 30)); }}Variante bipartida: maior função
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.