Búsqueda binaria

En este tutorial, aprenderá cómo funciona la clasificación de búsqueda binaria. Además, encontrará ejemplos prácticos de búsqueda binaria en C, C ++, Java y Python.

La búsqueda binaria es un algoritmo de búsqueda para encontrar la posición de un elemento en una matriz ordenada.

En este enfoque, el elemento siempre se busca en medio de una parte de una matriz.

La búsqueda binaria solo se puede implementar en una lista ordenada de elementos. Si los elementos aún no están ordenados, primero debemos ordenarlos.

Trabajo de búsqueda binaria

El algoritmo de búsqueda binaria se puede implementar de dos formas que se describen a continuación.

  1. Método iterativo
  2. Método recursivo

El método recursivo sigue el enfoque de divide y vencerás.

Los pasos generales para ambos métodos se analizan a continuación.

  1. El arreglo en el que se va a realizar la búsqueda es: Arreglo inicial
    Sea x = 4el elemento a buscar.
  2. Establezca dos punteros bajo y alto en las posiciones más baja y más alta, respectivamente. Establecer punteros
  3. Encuentre el elemento medio en el medio de la matriz, es decir. (arr(low + high)) / 2 = 6. Elemento medio
  4. Si x == mid, devuelve mid. De lo contrario, compare el elemento que se buscará con m.
  5. Si x> mid, compare x con el elemento central de los elementos del lado derecho de mid. Esto se hace estableciendo un valor bajo en low = mid + 1.
  6. De lo contrario, compare x con el elemento central de los elementos en el lado izquierdo de mid. Esto se hace estableciendo alto en high = mid - 1. Encontrar elemento medio
  7. Repita los pasos 3 a 6 hasta que lo bajo se encuentre con lo alto. Elemento medio
  8. x = 4es encontrado. Encontró

Algoritmo de búsqueda binaria

Método de iteración

hazlo hasta que los punteros bajo y alto se encuentren. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x está en el lado derecho low = mid + 1 else // x está en el lado izquierdo alto = medio - 1

Método recursivo

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

Ejemplos 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); )

Ejemplos 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); )

Complejidad de búsqueda binaria

Complejidades de tiempo

  • Mejor complejidad de caso :O(1)
  • Complejidad de caso promedio :O(log n)
  • Peor complejidad del caso :O(log n)

Complejidad espacial

La complejidad espacial de la búsqueda binaria es O(n).

Aplicaciones de búsqueda binaria

  • En bibliotecas de Java, .Net, C ++ STL
  • Durante la depuración, la búsqueda binaria se utiliza para identificar el lugar donde ocurre el error.

Articulos interesantes...