Punto de inserción inferior

Dada una array arr[] de n elementos enteros ordenados y un entero X , la tarea es encontrar el punto de inserción inferior de X en la array. El punto de inserción inferior es el índice del primer elemento que es ≥ X . Si X es mayor que todos los elementos de arr , imprima n y si X es menor que todos los elementos de arr[], devuelva 0 .
Ejemplos: 
 

Entrada: arr[] = {2, 3, 4, 4, 5, 6, 7, 9}, X = 4 
Salida: 2
Entrada: arr[] = {0, 5, 8, 15}, X = 16 
Salida : 4 
 

Acercarse: 
 

• Si X < arr[0] imprime 0 o X > arr[n – 1] imprime n .
• Inicialice lowertPnt = 0 y comience a recorrer la array de 1 a n – 1 . 
  • Si arr[i] < X entonces actualice lowerPnt = i y i = i * 2 .
  • El primer valor de i para el que X ≥ arr[i] o cuando i ≥ n , sale del bucle.
  • Ahora verifique el resto de los elementos desde lowerPnt hasta n – 1 , mientras que arr[lowerPnt] < X actualice lowerPnt = lowerPnt + 1.
  • Imprime lowerPnt al final..

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

// C++ program to find the lower insertion point
// of an element in a sorted array
#include <iostream>
using namespace std;
 
// Function to return the lower insertion point
// of an element in a sorted array
int LowerInsertionPoint(int arr[], int n, int X)
{
 
    // Base cases
    if (X < arr[0])
        return 0;
    else if (X > arr[n - 1])
        return n;
 
    int lowerPnt = 0;
    int i = 1;
 
    while (i < n && arr[i] < X) {
        lowerPnt = i;
        i = i * 2;
    }
 
    // Final check for the remaining elements which are < X
    while (lowerPnt < n && arr[lowerPnt] < X)
        lowerPnt++;
 
    return lowerPnt;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 4, 4, 5, 6, 7, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int X = 4;
    cout << LowerInsertionPoint(arr, n, X);
    return 0;
}

//Java program to find the lower insertion point
//of an element in a sorted array
public class AQES {
 
    //Function to return the lower insertion point
    //of an element in a sorted array
    static int LowerInsertionPoint(int arr[], int n, int X)
    {
 
     // Base cases
     if (X < arr[0])
         return 0;
     else if (X > arr[n - 1])
         return n;
 
     int lowerPnt = 0;
     int i = 1;
 
     while (i < n && arr[i] < X) {
         lowerPnt = i;
         i = i * 2;
     }
 
     // Final check for the remaining elements which are < X
     while (lowerPnt < n && arr[lowerPnt] < X)
         lowerPnt++;
 
     return lowerPnt;
    }
 
    //Driver code
    public static void main(String[] args) {
         
         int arr[] = { 2, 3, 4, 4, 5, 6, 7, 9 };
         int n = arr.length;
         int X = 4;
         System.out.println(LowerInsertionPoint(arr, n, X));
 
    }
}

# Python3 program to find the lower insertion
# point of an element in a sorted array
 
# Function to return the lower insertion
# point of an element in a sorted array
def LowerInsertionPoint(arr, n, X) :
 
    # Base cases
    if (X < arr[0]) :
        return 0;
    elif (X > arr[n - 1]) :
        return n
 
    lowerPnt = 0
    i = 1
 
    while (i < n and arr[i] < X) :
        lowerPnt = i
        i = i * 2
 
    # Final check for the remaining elements
    # which are < X
    while (lowerPnt < n and arr[lowerPnt] < X) :
        lowerPnt += 1
 
    return lowerPnt
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 2, 3, 4, 4, 5, 6, 7, 9 ]
    n = len(arr)
    X = 4
    print(LowerInsertionPoint(arr, n, X))
 
# This code is contributed by Ryuga

// C#  program to find the lower insertion point
//of an element in a sorted array
using System;
 
public class GFG{
    //Function to return the lower insertion point
    //of an element in a sorted array
    static int LowerInsertionPoint(int []arr, int n, int X)
    {
 
    // Base cases
    if (X < arr[0])
        return 0;
    else if (X > arr[n - 1])
        return n;
 
    int lowerPnt = 0;
    int i = 1;
 
    while (i < n && arr[i] < X) {
        lowerPnt = i;
        i = i * 2;
    }
 
    // Final check for the remaining elements which are < X
    while (lowerPnt < n && arr[lowerPnt] < X)
        lowerPnt++;
 
    return lowerPnt;
    }
 
    //Driver code
    static public void Main (){
        int []arr = { 2, 3, 4, 4, 5, 6, 7, 9 };
        int n = arr.Length;
        int X = 4;
        Console.WriteLine(LowerInsertionPoint(arr, n, X));
    }
}

<?php
// PHP program to find the lower insertion
// point of an element in a sorted array
 
// Function to return the lower insertion
// point of an element in a sorted array
function LowerInsertionPoint($arr, $n, $X)
{
 
    // Base cases
    if ($X < $arr[0])
        return 0;
    else if ($X > $arr[$n - 1])
        return $n;
 
    $lowerPnt = 0;
    $i = 1;
 
    while ($i < $n && $arr[$i] < $X)
    {
        $lowerPnt = $i;
        $i = $i * 2;
    }
 
    // Final check for the remaining
    // elements which are < X
    while ($lowerPnt < $n && $arr[$lowerPnt] < $X)
        $lowerPnt++;
 
    return $lowerPnt;
}
 
// Driver code
$arr = array( 2, 3, 4, 4, 5, 6, 7, 9 );
$n = sizeof($arr);
$X = 4;
echo LowerInsertionPoint($arr, $n, $X);
 
// This code is contributed by ajit.
?>

<script>
 
    // Javascript program to find the lower insertion point
    // of an element in a sorted array
     
    // Function to return the lower insertion point
    // of an element in a sorted array
    function LowerInsertionPoint(arr, n, X)
    {
       
        // Base cases
        if (X < arr[0])
            return 0;
        else if (X > arr[n - 1])
            return n;
       
        let lowerPnt = 0;
        let i = 1;
       
        while (i < n && arr[i] < X) {
            lowerPnt = i;
            i = i * 2;
        }
       
        // Final check for the remaining elements which are < X
        while (lowerPnt < n && arr[lowerPnt] < X)
            lowerPnt++;
       
        return lowerPnt;
    } 
     
    let arr = [ 2, 3, 4, 4, 5, 6, 7, 9 ];
    let n = arr.length;
    let X = 4;
    document.write(LowerInsertionPoint(arr, n, X));
     
</script>

2

Optimización adicional: la complejidad temporal de la solución anterior puede convertirse en O(n) en el peor de los casos. Podemos optimizar la solución para que funcione en tiempo O (Log n) utilizando la búsqueda binaria. Consulte la búsqueda binaria ilimitada para obtener más detalles.