Abstracción de búsqueda binaria

¿Qué es el algoritmo de búsqueda binaria? 
El algoritmo de búsqueda binaria se utiliza para encontrar un cierto valor de x para el cual una cierta función definida f(x) necesita ser maximizada o minimizada. Se utiliza con frecuencia para buscar un elemento en una secuencia ordenada dividiendo repetidamente el intervalo de búsqueda en dos mitades. Comience con un intervalo que cubra toda la secuencia, si el valor de la clave de búsqueda es menor que el elemento en el medio del intervalo, busque en la mitad izquierda del intervalo; de lo contrario, busque en la mitad derecha. Verifique repetidamente hasta que se encuentre el valor o el intervalo esté vacío. 
La principal condición para realizar una Búsqueda Binaria es que la secuencia debe ser monótona, es decir, debe ser creciente o decreciente.  

Función monótona 
Se dice que una función f(x) es monótona si y solo si para cualquier x si f(x) devuelve verdadero, entonces para cualquier valor de y (donde y > x) también debe devolver verdadero y de manera similar si para un cierto valor de x para el cual f(x) es falso, entonces para cualquier valor z (z < x) la función también debería devolver falso. 
 

Cómo resolver una pregunta usando la búsqueda binaria: 
si la función es 

Y la tarea es encontrar el valor máximo de x tal que f(x) sea menor o igual que el valor objetivo . El intervalo en el que buscaremos el valor objetivo para el dado 

es de 0 al valor objetivo . 
Entonces podemos usar la búsqueda binaria para este problema ya que la función 

es una función monótonamente creciente. 

Target = 17 
f(x) = x ² , dado que la función es monótona, se le puede aplicar una búsqueda binaria. 
El rango del intervalo de búsqueda será [0, objetivo]
Paso 1: 
bajo = 0, alto = 17, calcular medio = (bajo + alto)/2 = 8 
Calcular f(8) = 64, que es más que el objetivo, por lo que devuelve false y high se actualizará como high = mid – 1 = 7.
Pasos 2: 
low = 0, high = 7, calcule mid = (low + high)/2 = 3 
Calcule f(3) = 9, que es menor que objetivo, por lo que devolverá verdadero y bajo se actualizará como bajo = medio + 1 = 4.
Paso 3: 
bajo = 4, alto = 7, calcule medio = (bajo + alto)/2 = 5 
Calcule f (5) = 25, que es más que el objetivo, por lo que devolverá falso y alto se actualizará como alto = medio – 1 = 4.
Paso 4: 
Ahora, dado que el rango [bajo, alto] converge en un solo punto, es decir 4 por lo que se encuentra el resultado final, ya que f(4) = 16 que es el valor máximo de la función dada menos que el objetivo. 
 

A continuación se muestra la implementación del ejemplo anterior:
 

// C++ program for the above example
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to find X such that it is
// less than the target value and function
// is f(x) = x^2
void findX(int targetValue)
{
 
    // Initialise start and end
    int start = 0, end = targetValue;
    int mid, result;
 
    // Loop till start <= end
    while (start <= end) {
 
        // Find the mid
        mid = start + (end - start) / 2;
 
        // Check for the left half
        if (mid * mid <= targetValue) {
 
            // Store the result
            result = mid;
 
            // Reinitialize the start point
            start = mid + 1;
        }
 
        // Check for the right half
        else {
            end = mid - 1;
        }
    }
 
    // Print the maximum value of x
    // such that x^2 is less than the
    // targetValue
    cout << result << endl;
}
 
// Driver Code
int main()
{
    // Given targetValue;
    int targetValue = 81;
 
    // Function Call
    findX(targetValue);
}

// Java program for
// the above example
import java.util.*;
class GFG{
 
// Function to find X such
// that it is less than the
// target value and function
// is f(x) = x^2
static void findX(int targetValue)
{
     
    // Initialise start and end
    int start = 0, end = targetValue;
    int mid = 0, result = 0;
 
    // Loop till start <= end
    while (start <= end)
    {
         
        // Find the mid
        mid = start + (end - start) / 2;
 
        // Check for the left half
        if (mid * mid <= targetValue)
        {
 
            // Store the result
            result = mid;
 
            // Reinitialize the start point
            start = mid + 1;
        }
 
        // Check for the right half
        else
        {
            end = mid - 1;
        }
    }
 
    // Print the maximum value of x
    // such that x^2 is less than the
    // targetValue
    System.out.print(result + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given targetValue;
    int targetValue = 81;
 
    // Function call
    findX(targetValue);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for
# the above example
 
# Function to find X such
# that it is less than the
# target value and function
# is f(x) = x ^ 2
def findX(targetValue):
   
    # Initialise start and end
    start = 0;
    end = targetValue;
    mid = 0;
 
    # Loop till start <= end
    while (start <= end):
       
        # Find the mid
        mid = start + (end - start) // 2;
 
        # Check for the left half
        if (mid * mid <= targetValue):
            result = mid
            start = mid + 1;
 
        # Check for the right half
        else:
            end = mid - 1;
 
    # Print maximum value of x
    # such that x ^ 2 is less than the
    # targetValue
    print(result);
 
# Driver Code
if __name__ == '__main__':
   
    # Given targetValue;
    targetValue = 81;
 
    # Function Call
    findX(targetValue);
 
# This code is contributed by Rajput-Ji

// C# program for
// the above example
using System;
class GFG{
 
// Function to find X such
// that it is less than the
// target value and function
// is f(x) = x^2
static void findX(int targetValue)
{
     
    // Initialise start and end
    int start = 0, end = targetValue;
    int mid = 0, result = 0;
 
    // Loop till start <= end
    while (start <= end)
    {
         
        // Find the mid
        mid = start + (end - start) / 2;
 
        // Check for the left half
        if (mid * mid <= targetValue)
        {
 
            // Store the result
            result = mid;
 
            // Reinitialize the start point
            start = mid + 1;
        }
 
        // Check for the right half
        else
        {
            end = mid - 1;
        }
    }
     
    // Print the maximum value of x
    // such that x^2 is less than the
    // targetValue
    Console.Write(result + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given targetValue;
    int targetValue = 81;
 
    // Function Call
    findX(targetValue);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
 
// JavaScript program for the above example
 
// Function to find X such that it is
// less than the target value and function
// is f(x) = x^2
function findX(targetValue)
{
 
    // Initialise start and end
    var start = 0, end = targetValue;
    var mid, result;
 
    // Loop till start <= end
    while (start <= end) {
 
        // Find the mid
        mid = start + parseInt((end - start) / 2);
 
        // Check for the left half
        if (mid * mid <= targetValue) {
 
            // Store the result
            result = mid;
 
            // Reinitialize the start point
            start = mid + 1;
        }
 
        // Check for the right half
        else {
            end = mid - 1;
        }
    }
 
    // Print the maximum value of x
    // such that x^2 is less than the
    // targetValue
    document.write( result );
}
 
// Driver Code
 
// Given targetValue;
var targetValue = 81;
 
// Function Call
findX(targetValue);
 
 
</script>

9

El algoritmo de búsqueda binaria anterior requiere como máximo comparaciones O (log N) para encontrar el valor máximo menor o igual que el valor objetivo. Y el valor de la función f(x) = x ² no necesita ser evaluado muchas veces.
Complejidad temporal: O(logN) 
Espacio auxiliar: O(1)