La búsqueda binaria es un algoritmo que nos ayuda a encontrar un elemento en una array ordenada en tiempo O (log n). Su algoritmo funciona según el principio de Divide y vencerás y funciona solo cuando se ordenan los datos disponibles.
Ahora, cuando estamos usando la búsqueda binaria surgen tres situaciones:
- Si el elemento del medio es el elemento a buscar, devolvemos el índice del elemento del medio.
- Si el elemento del medio es más pequeño que el elemento que se va a buscar, buscamos en el subconjunto de la derecha (Mid to End) de la misma manera (Obtenga el nuevo medio y verifique los tres casos nuevamente). Buscamos en el subarreglo derecho porque los datos están ordenados, por lo tanto, todos los elementos antes del elemento central también serán menores o iguales que el elemento central.
- Si el elemento del medio es mayor que el elemento que se va a buscar, buscamos en el subconjunto de la izquierda (de inicio a medio).
Este proceso continúa hasta que encontramos el elemento a buscar o el tamaño de la sub-array se reduce a cero.
Ejemplo:
Hay tres formas de realizar la búsqueda binaria en Scala.
Enfoque recursivo
En el enfoque recursivo, solicitamos recursivamente el algoritmo de búsqueda binaria implementado con valores actualizados de inicio y final hasta que hagamos coincidir el elemento central con el elemento que se busca o el tamaño de la array se reduzca a cero. A continuación se muestra el código para el enfoque recursivo de la búsqueda binaria en Scala.
// Scala code for Recursive Binary Search
// Creating object
object GFG{
// Creating a recursive Binary Search function
def RecursiveBinarySearch(arr: Array[Int],
Element_to_Search: Int)
(low: Int = 0,
high: Int = arr.length - 1): Int =
{
// If element not found
if (low > high)
return -1
// Getting the middle element
var middle = low + (high - low) / 2
// If element found
if (arr(middle) == Element_to_Search)
return middle
// Searching in the left half
else if (arr(middle) > Element_to_Search)
return RecursiveBinarySearch(arr,
Element_to_Search)(low, middle - 1)
// Searching in the right half
else
return RecursiveBinarySearch(arr,
Element_to_Search)(middle + 1, high)
}
// Creating main function
def main(args: Array[String]){
// Calling the binary search function and
// storing its result in index variable
var index = RecursiveBinarySearch(Array(1, 2, 3, 4, 55,
65, 75), 4)(0, 6);
// If value not found
if(index == -1)
print("Not Found")
// Else print the index where
// the value is found
else
print("Element found at Index " + index)
}
}
Producción
Element found at Index 3
Enfoque iterativo
En el enfoque iterativo, ejecutamos un ciclo while hasta que encontramos el elemento a buscar o el tamaño de la array se reduce a cero. A continuación se muestra el código para el enfoque iterativo de la búsqueda binaria en Scala.
// Scala code for Iterative Binary Search
// Creating object
object GFG{
// Creating Binary Search function
// Accepting the passed array and
// element to be searched
def IterativeBinarySearch(arr: Array[Int],
Element_to_Search: Int): Int =
{
// Creating start variable to
// point to the first value
var low = 0
// Creating end variable to
// point to the last value
var high = arr.length - 1
// Finding the value in the
// array iteratively
while (low <= high)
{
// Getting middle element
var middle = low + (high - low) / 2
// If element found in the middle index
if (arr(middle) == Element_to_Search)
return middle
// Searching in the first half
else if (arr(middle) > Element_to_Search)
high = middle - 1
// Searching in the second half
else
low = middle + 1
}
// If value not found in the
// entire array , return -1
-1
}
// Creating main function
def main(args: Array[String])
{
// Calling the binary search function and
// storing its result in index variable
var index = IterativeBinarySearch(Array(1, 2, 3, 4, 55,
65, 75), 65);
// If value not found
if(index == -1)
print("Not Found")
// Else print the index where
// the value is found
else
print("Element found at Index " + index)
}
}
< Salida
Element found at Index 5
Coincidencia de patrones y enfoque de programación funcional
En esto, primero hacemos coincidir el elemento del medio con el elemento a buscar. Si el elemento está presente, devolvemos el índice del mismo. De lo contrario, seguimos llamando a la función creada con los parámetros actualizados. A continuación se muestra el código para el enfoque:
// Scala code for Iterative Binary Search
// Creating object
object GFG{
// Using the functional programming approach
def FunctionalBinarySearch(arr: Array[Int],
Element_to_Search: Int): Int =
{
def BinarySearch(arr: Array[Int],
Element_to_Search: Int,
low: Int, high: Int): Int =
{
// If element not found
if (low > high)
return -1
// Getting middle index
var middle = low + (high - low) / 2
// Pattern matching
arr match
{
// If element found , return the index
case(arr:Array[Int]) if (arr(middle) ==
Element_to_Search) =>
middle
// Call the function for the second half
case(arr:Array[Int]) if (arr(middle) <
Element_to_Search) =>
BinarySearch(arr,
Element_to_Search,
middle + 1, high)
// Call the function for the first half
case(arr:Array[Int]) if (arr(middle) >
Element_to_Search) =>
BinarySearch(arr,
Element_to_Search,
low, middle - 1)
}
}
// Calling the Binary Search function
BinarySearch(arr, Element_to_Search, 0, arr.length - 1)
}
// Creating main function
def main(args: Array[String]){
// Calling the binary search function and
// storing its result in index variable
var index = FunctionalBinarySearch(Array(1, 2, 3, 4, 55,
65, 75), 44);
// If value not found
if(index == -1)
print("Element not found")
// Else print the index where
// the value is found
else
print("Element found at Index " + index)
}
}
Producción
Element not found
Publicación traducida automáticamente
Artículo escrito por anmolsharmalbs y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA