Búsqueda binaria en JavaScript

La búsqueda binaria es una técnica de búsqueda que funciona con el enfoque Divide and Conquer . Se utiliza para buscar cualquier elemento en una array ordenada. 
En comparación con la búsqueda binaria lineal, es mucho más rápida con una complejidad de tiempo de O(logN), mientras que la búsqueda lineal funciona en una complejidad de tiempo O(N).
En este artículo, se analiza la implementación de la búsqueda binaria en Javascript utilizando formas iterativas y recursivas.
Dada una array ordenada de números. La tarea es buscar un elemento dado  en la array utilizando la búsqueda binaria.
Ejemplos : 
 

Input : arr[] = {1, 3, 5, 7, 8, 9}
        x = 5
Output : Element found!

Input : arr[] = {1, 3, 5, 7, 8, 9}
        x = 6
Output : Element not found!

Nota: Suponiendo que la array esté ordenada.
 

Enfoque recursivo: 
 

1. CONDICIÓN BASE: si el índice inicial es mayor que el índice final, devuelve falso.
2. Calcule el índice medio.
3. Compara el elemento del medio con el número x. Si es igual devuelve verdadero.
4. Si es mayor, llame a la misma función con índice final = medio-1 y repita el paso 1.
5. Si es más pequeño, llame a la misma función con índice inicial = medio + 1 y repita el paso 1.

A continuación se muestra la implementación de la búsqueda binaria (enfoque recursivo) en JavaScript: 
 

<script>
let recursiveFunction = function (arr, x, start, end) {
      
    // Base Condition
    if (start > end) return false;
  
    // Find the middle index
    let mid=Math.floor((start + end)/2);
  
    // Compare mid with given key x
    if (arr[mid]===x) return true;
         
    // If element at mid is greater than x,
    // search in the left half of mid
    if(arr[mid] > x)
        return recursiveFunction(arr, x, start, mid-1);
    else
 
        // If element at mid is smaller than x,
        // search in the right half of mid
        return recursiveFunction(arr, x, mid+1, end);
}
  
// Driver code
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;
  
if (recursiveFunction(arr, x, 0, arr.length-1))
    document.write("Element found!<br>");
else document.write("Element not found!<br>");
  
x = 6;
  
if (recursiveFunction(arr, x, 0, arr.length-1))
    document.write("Element found!<br>");
else document.write("Element not found!<br>");
</script>                                     

Salida : 
 

Element found!
Element not found!

Complejidad de tiempo: O(logN)
Espacio auxiliar: O(1) 
Enfoque iterativo: en este enfoque iterativo, en lugar de recursividad, usamos un ciclo while, y el ciclo se ejecuta hasta que alcanza la condición base, es decir, el inicio se vuelve mayor que el final.
A continuación se muestra la implementación de la búsqueda binaria (enfoque iterativo) en JavaScript: 
 

<script>
// Iterative function to implement Binary Search
let iterativeFunction = function (arr, x) {
  
    let start=0, end=arr.length-1;
         
    // Iterate while start not meets end
    while (start<=end){
 
        // Find the mid index
        let mid=Math.floor((start + end)/2);
  
        // If element is present at mid, return True
        if (arr[mid]===x) return true;
 
        // Else look in left or right half accordingly
        else if (arr[mid] < x)
             start = mid + 1;
        else
             end = mid - 1;
    }
  
    return false;
}
  
// Driver code
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;
  
if (iterativeFunction(arr, x, 0, arr.length-1))
    document.write("Element found!<br>");
else document.write("Element not found!<br>");
  
x = 6;
  
if (iterativeFunction(arr, x, 0, arr.length-1))
    document.write("Element found!<br>");
else document.write("Element not found!<br>");
</script>                                     

Salida : 
 

Element found!
Element not found!

Complejidad temporal: O(logN).
Espacio Auxiliar: O(1)