Problema: dada una array ordenada arr[] de n elementos, escriba una función para buscar un elemento dado x en arr[] y devuelva el índice de x en la array.
Considere que la array tiene un índice base 0.
Ejemplos:
Entrada: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
Salida: 6
Explicación: El elemento x está presente en el índice 6.Entrada: arr[] = {10, 20, 30, 40, 60, 110, 120, 130, 170}, x = 175
Salida: -1
Explicación: el elemento x no está presente en arr[].
Enfoque de búsqueda lineal : un enfoque simple es realizar una búsqueda lineal . La complejidad temporal de la búsqueda lineal es O(n). Otro enfoque para realizar la misma tarea es utilizar la búsqueda binaria .
Enfoque de búsqueda binaria:
La búsqueda binaria es un algoritmo de búsqueda que se utiliza en una array ordenada dividiendo repetidamente el intervalo de búsqueda por la mitad . La idea de la búsqueda binaria es usar la información de que la array está ordenada y reducir la complejidad del tiempo a O (Log n).
Algoritmo de Búsqueda Binaria: Los pasos básicos para realizar la Búsqueda Binaria son:
- Comience con el elemento medio de toda la array como clave de búsqueda.
- Si el valor de la clave de búsqueda es igual al elemento, devuelva un índice de la clave de búsqueda.
- O si el valor de la clave de búsqueda es menor que el elemento en el medio del intervalo, reduzca el intervalo a la mitad inferior.
- De lo contrario, redúcelo a la mitad superior.
- Verifique repetidamente desde el segundo punto hasta que se encuentre el valor o el intervalo esté vacío.
El algoritmo de búsqueda binaria se puede implementar de las siguientes dos maneras
- Método iterativo
- Método recursivo
1. Método de iteración
binarySearch(arr, x, low, high)
repeat till low = high
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
2. Método recursivo (El método recursivo sigue el enfoque divide y vencerás)
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the right side
return binarySearch(arr, x, low, mid - 1)
Ilustración del algoritmo de búsqueda binaria:
Ejemplo de algoritmo de búsqueda binaria
Algoritmo de búsqueda binaria paso a paso: básicamente ignoramos la mitad de los elementos justo después de una comparación.
- Compara x con el elemento del medio.
- Si x coincide con el elemento medio, devolvemos el índice medio.
- De lo contrario, si x es mayor que el elemento medio, entonces x solo puede estar en el medio subarreglo derecho después del elemento medio. Entonces recurrimos a la mitad derecha.
- De lo contrario (x es menor) se repite para la mitad izquierda.
Implementación recursiva de búsqueda binaria :
C++
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
C
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Java
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[l..
// r], else return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "
+ result);
}
}
/* This code is contributed by Rajat Mishra */
Python3
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch(arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index % d" % result)
else:
print("Element is not present in array")
C#
// C# implementation of recursive Binary Search
using System;
class GFG {
// Returns index of x if it is present in
// arr[l..r], else return -1
static int binarySearch(int[] arr, int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
Console.WriteLine("Element not present");
else
Console.WriteLine("Element found at index "
+ result);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to implement
// recursive Binary Search
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
function binarySearch($arr, $l, $r, $x)
{
if ($r >= $l)
{
$mid = ceil($l + ($r - $l) / 2);
// If the element is present
// at the middle itself
if ($arr[$mid] == $x)
return floor($mid);
// If element is smaller than
// mid, then it can only be
// present in left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element can only
// be present in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// We reach here when element
// is not present in array
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = binarySearch($arr, 0, $n - 1, $x);
if(($result == -1))
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x){
if (r >= l) {
let mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? document.write( "Element is not present in array")
: document.write("Element is present at index " +result);
</script>
Element is present at index 3
Complejidad de Tiempo: O(log n)
Espacio Auxiliar: O(log n)
Otro enfoque iterativo para la búsqueda binaria
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int binarySearch(vector<int> v, int To_Find)
{
int lo = 0, hi = v.size() - 1;
int mid;
// This below check covers all cases , so need to check
// for mid=lo-(hi-lo)/2
while (hi - lo > 1) {
int mid = (hi + lo) / 2;
if (v[mid] < To_Find) {
lo = mid + 1;
}
else {
hi = mid;
}
}
if (v[lo] == To_Find) {
cout << "Found"
<< " At Index " << lo << endl;
}
else if (v[hi] == To_Find) {
cout << "Found"
<< " At Index " << hi << endl;
}
else {
cout << "Not Found" << endl;
}
}
int main()
{
vector<int> v = { 1, 3, 4, 5, 6 };
int To_Find = 1;
binarySearch(v, To_Find);
To_Find = 6;
binarySearch(v, To_Find);
To_Find = 10;
binarySearch(v, To_Find);
return 0;
}
Found At Index 0 Found At Index 4 Not Found
Tiempo Complejidad: O (log n)
Espacio Auxiliar: O (1)
Implementación iterativa de búsqueda binaria
C++
// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
C
// C program to implement iterative Binary Search
#include <stdio.h>
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return 0;
}
Java
// Java implementation of iterative Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
Python3
# Python3 code to implement iterative Binary
# Search.
# It returns location of x in given array arr
# if present, else returns -1
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 2
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index % d" % result)
else:
print("Element is not present in array")
C#
// C# implementation of iterative Binary Search
using System;
class GFG {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(int[] arr, int x)
{
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
Console.WriteLine("Element not present");
else
Console.WriteLine("Element found at "
+ "index " + result);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to implement
// iterative Binary Search
// A iterative binary search
// function. It returns location
// of x in given array arr[l..r]
// if present, otherwise -1
function binarySearch($arr, $l,
$r, $x)
{
while ($l <= $r)
{
$m = $l + ($r - $l) / 2;
// Check if x is present at mid
if ($arr[$m] == $x)
return floor($m);
// If x greater, ignore
// left half
if ($arr[$m] < $x)
$l = $m + 1;
// If x is smaller,
// ignore right half
else
$r = $m - 1;
}
// if we reach here, then
// element was not present
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = binarySearch($arr, 0,
$n - 1, $x);
if(($result == -1))
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Program to implement iterative Binary Search
// A iterative binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, x)
{
let l = 0;
let r = arr.length - 1;
let mid;
while (r >= l) {
mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
r = mid - 1;
// Else the element can only be present
// in right subarray
else
l = mid + 1;
}
// We reach here when element is not
// present in array
return -1;
}
arr =new Array(2, 3, 4, 10, 40);
x = 10;
n = arr.length;
result = binarySearch(arr, x);
(result == -1) ? document.write("Element is not present in array")
: document.write ("Element is present at index " + result);
// This code is contributed by simranarora5sos and rshuklabbb
</script>
Element is present at index 3
Complejidad temporal: O(log n)
Espacio auxiliar: O(1)
Paradigma algorítmico: disminuir y conquistar .
Nota: Aquí estamos usando
int mid = bajo + (alto – bajo)/2;
Tal vez se pregunte por qué estamos calculando el índice medio de esta manera, simplemente podemos sumar el índice inferior y superior y dividirlo por 2.
int mid = (bajo + alto)/2;
Pero si calculamos el índice medio así, significa que nuestro código no es 100% correcto, contiene errores.
Es decir, falla para valores más grandes de variables int bajas y altas. Específicamente, falla si la suma de alto y bajo es mayor que el valor int positivo máximo (2 31 – 1).
La suma se desborda a un valor negativo y el valor se mantiene negativo cuando se divide por 2.
En java, lanza ArrayIndexOutOfBoundException.
int mid = bajo + (alto – bajo)/2;
Así que es mejor usarlo así. Este error se aplica igualmente a la combinación de clasificación y otros algoritmos de dividir y conquistar.
Cursos GeeksforGeeks:
1. Language Foundation Courses [ C++ / JAVA / Python ]
Aprenda cualquier lenguaje de programación desde cero y comprenda todos sus conceptos fundamentales para una sólida base de programación de la manera más fácil posible con la ayuda de GeeksforGeeks Language Foundation Courses – Java Foundation | Fundación Python | C++ Foundation
2. Geeks Classes Live
Obtenga clases en línea en vivo centradas en entrevistas sobre estructura de datos y algoritmos desde cualquier ubicación geográfica para aprender y dominar los conceptos de DSA para mejorar sus habilidades de programación y resolución de problemas y para descifrar la entrevista de cualquier empresa basada en productos: Clases Geeks: Sesión en Vivo
3.Preparación completa para entrevistas
Cumple con todas tus necesidades de preparación para entrevistas en un solo lugar con el Curso completo de preparación para entrevistas que te proporciona todo lo necesario para prepararte para cualquier empresa basada en productos, servicios o puesta en marcha a los precios más asequibles.
4. DSA a su propio ritmo
Comience a aprender estructuras de datos y algoritmos para prepararse para las entrevistas de los principales gigantes de TI como Microsoft, Amazon, Adobe, etc. con el curso de DSA a su propio ritmo, donde podrá aprender y dominar DSA desde el nivel básico hasta el avanzado y eso también a su propio ritmo y conveniencia.
5. Cursos específicos de la empresa: Amazon , Microsoft , TCS y Wipro
Resuelva la entrevista de cualquier empresa gigante basada en productos preparándose específicamente con las preguntas que estas empresas suelen hacer en su ronda de entrevistas de codificación. Consulte los cursos específicos de GeeksforGeeks Company: Amazon SDE Test Series , etc.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA