Pesquisa Binária

Neste tutorial, você aprenderá como funciona a classificação por pesquisa binária. Além disso, você encontrará exemplos funcionais de pesquisa binária em C, C ++, Java e Python.

A pesquisa binária é um algoritmo de pesquisa para encontrar a posição de um elemento em uma matriz classificada.

Nessa abordagem, o elemento é sempre pesquisado no meio de uma parte de uma matriz.

A pesquisa binária pode ser implementada apenas em uma lista classificada de itens. Se os elementos ainda não estiverem classificados, precisamos classificá-los primeiro.

Trabalho de pesquisa binária

O algoritmo de pesquisa binária pode ser implementado de duas maneiras, as quais são discutidas abaixo.

  1. Método Iterativo
  2. Método Recursivo

O método recursivo segue a abordagem de dividir e conquistar.

As etapas gerais para ambos os métodos são discutidas abaixo.

  1. A matriz na qual a pesquisa deve ser realizada é: Matriz inicial
    Seja x = 4o elemento a ser pesquisado.
  2. Defina dois ponteiros baixo e alto nas posições mais baixa e mais alta, respectivamente. Definindo ponteiros
  3. Encontre o elemento do meio no meio da matriz, ou seja. (arr(low + high)) / 2 = 6. Elemento médio
  4. Se x == mid, então retorna mid.Else, compare o elemento a ser pesquisado com m.
  5. Se x> mid, compare x com o elemento do meio dos elementos no lado direito do meio. Isso é feito definindo como baixo low = mid + 1.
  6. Caso contrário, compare x com o elemento do meio dos elementos no lado esquerdo do meio. Isso é feito configurando-se como alto high = mid - 1. Encontrando o elemento médio
  7. Repita os passos 3 a 6 até que o baixo encontre o alto. Elemento médio
  8. x = 4seja encontrado. Encontrado

Algoritmo de pesquisa binária

Método de Iteração

faça até que os ponteiros baixo e alto se encontrem. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x está no lado direito low = mid + 1 else // x está ativado o lado esquerdo alto = médio - 1

Método Recursivo

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 se x == arr (mid) return mid else if x <data (mid) // x está no lado direito return binarySearch (arr, x, mid + 1, high) else // x está no lado direito return binarySearch (arr, x, low, mid - 1)

Exemplos de Python, Java, C / C ++ (método iterativo)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Exemplos de Python, Java, C / C ++ (método recursivo)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Complexidade de pesquisa binária

Complexidades de tempo

  • Melhor caso de complexidade :O(1)
  • Complexidade média do caso :O(log n)
  • Pior caso de complexidade :O(log n)

Complexidade do Espaço

A complexidade espacial da busca binária é O(n).

Aplicativos de pesquisa binária

  • Em bibliotecas de Java, .Net, C ++ STL
  • Durante a depuração, a pesquisa binária é usada para localizar o local onde o erro ocorre.

Artigos interessantes...