Java Binary Search interativo e recursivo

Harshit Jindal 12 outubro 2023 Java Java Algorithm
  1. Algoritmo de pesquisa binária iterativa
  2. Programa iterativo Java para pesquisa binária
  3. Algoritmo de pesquisa binária recursiva
  4. Programa Java Recursivo para Pesquisa Binária
  5. Arrays.binarySearch() Visão geral
  6. Programa Java para Pesquisa Binária
Java Binary Search interativo e recursivo

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
Está gostando dos nossos tutoriais? Inscreva-se no DelftStack no YouTube para nos apoiar na criação de mais vídeos tutoriais de alta qualidade. Inscrever-se
Autor: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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.

LinkedIn