HOWTO · Java

Java Binary Search interativo e recursivo

Este tutorial demonstra como usar o algoritmo de pesquisa binária.

Por Harshit JindalPublicado 2021-03-30Atualizado 2023-10-12

Algoritmo de pesquisa binária iterativa

Vamos supor que temos um array não classificado A[] contendo n elementos, e queremos encontrar um elemento X.

  • Defina lo como 0 e hi como n - 1.
  • Enquanto lo <hi:
    • Defina mid = lo + (hi - lo)/2.
    • Se A[mid] == X, encontramos o elemento que retorna o índice mid.
    • Se A[mid] < X, descarte a metade esquerda dos elementos e defina lo como mid+1.
    • Caso contrário, se A[mid] > X, descarte a metade direita dos elementos e defina hi como mid-1.
  • Elemento não encontrado, então retorne -1.

Programa iterativo Java para pesquisa binária

class BinarySearch {
  int binarySearch(int arr[], int x) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;

      if (arr[mid] == x)
        return mid;

      if (arr[mid] < x)
        lo = mid + 1;

      else
        hi = mid - 1;
    }
    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {1, 2, 3, 4, 5};
    int n = arr.length;
    int x = 5;
    int position = ob.binarySearch(arr, x);
    if (position == -1)
      System.out.println("Element not present");
    else
      System.out.println("Element found at index: " + position);
  }
}

Resultado:

Element found at index: 4

Algoritmo de pesquisa binária recursiva

Vamos supor que temos um array não classificado A[] contendo n elementos, e queremos encontrar um elemento X.

  • Inicialize lo como 0 e hi como n-1.
  • se lo > hi, esgotamos o espaço de pesquisa do array, retorna -1.
  • Calcule o ponto médio mid como lo+(hi-lo)/2. Ele divide a matriz em duas partes: a metade inferior com elementos de 0 a mid - 1 e a metade superior com elementos de mid a n - 1.
  • Se X == mid, encontramos o retorno do elemento de destino mid.
  • Se X for menor que mid, pesquise a metade inferior do array chamando recursivamente binarysearch(arr, lo, mid-1).
  • Caso contrário, se X for maior que mid, pesquise a metade superior do array chamando recursivamente binarysearch(arr, mid+1, hi).

Programa Java Recursivo para Pesquisa Binária

class BinarySearch {
  int binarySearch(int arr[], int lo, int hi, int x) {
    if (hi >= lo && lo < arr.length - 1) {
      int mid = lo + (hi - lo) / 2;
      if (arr[mid] == x)
        return mid;
      if (arr[mid] > x)
        return binarySearch(arr, lo, mid - 1, x);
      return binarySearch(arr, mid + 1, hi, x);
    }
    return -1;
  }
  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {1, 2, 3, 4, 5};
    int n = arr.length;
    int x = 2;
    int position = ob.binarySearch(arr, 0, n - 1, x);
    if (position == -1)
      System.out.println("Element not found !!!");
    else
      System.out.println("Element found at index: " + position);
  }
}

Resultado:

Element found at index: 1

Arrays.binarySearch() Visão geral

Java nos fornece uma função pronta para usar Arrays.binarySearch() para que não tenhamos que implementar a função nós mesmos. É um método muito simples de usar e implementado de forma eficiente e não está sujeito a erros.

Sintaxe

public static int binarySearch(T arr, T key)

T pode ser qualquer um dos seguintes:int, float, short, long, byte, char, double, e até mesmo um Object definido pelo usuário também.

Assim como nossa pesquisa binária implementada, ela também requer que a matriz seja classificada, caso contrário, os resultados serão indefinidos. Ele pesquisa a matriz usando o algoritmo de pesquisa binária e encontra o índice do elemento de destino. Se houver várias ocorrências do elemento de destino, ele pode retornar o índice de qualquer um deles.

Parâmetros
Arr A matriz de entrada
Key O elemento de destino que estamos procurando.

Retornar

Se ele encontrar o elemento de destino, ele retornará seu índice. Caso contrário, ele retorna beg - 1 onde beg é o índice inicial do espaço de busca do array.

Programa Java para Pesquisa Binária

import java.util.Arrays;

class BinarySearchExample {
  public static void main(String args[]) {
    int arr[] = {1, 2, 3, 4, 5};
    int key = 2;
    int result = Arrays.binarySearch(arr, key);
    if (result < 0)
      System.out.println("Element is not found!");
    else
      System.out.println("Element is found at index: " + result);
  }
}

Resultado:

Element is found at index: 1

Sobre o autor

Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

Ver perfil do autor
LinkedIn