Primer elemento estrictamente más pequeño en una array ordenada en Java

Dada una array ordenada y un valor objetivo, encuentre el primer elemento que sea estrictamente más pequeño que el elemento dado.
Ejemplos: 
 

Input : arr[] = {1, 2, 3, 5, 8, 12} 
        Target = 5
Output : 2 (Index of 3)

Input : {1, 2, 3, 5, 8, 12} 
        Target = 8
Output : 3 (Index of 5)

Input : {1, 2, 3, 5, 8, 12} 
        Target = 15
Output : -1

Una solución simple es recorrer linealmente la array dada y encontrar el primer elemento que sea estrictamente mayor. Si no existe tal elemento, devuelva -1.
Una solución eficiente es usar Binary Search . En una búsqueda binaria general, buscamos un valor que aparece en la array. A veces, sin embargo, necesitamos encontrar el primer elemento que sea mayor que un objetivo.
Para ver que este algoritmo es correcto, considere cada comparación que se realiza. Si encontramos un elemento que es mayor que el elemento de destino, entonces él y todo lo que está por encima de él no pueden coincidir, por lo que no hay necesidad de buscar en esa región. Así podemos buscar la mitad izquierda. Si encontramos un elemento que es más pequeño que el elemento en cuestión, entonces cualquier elemento anterior también debe ser más grande, por lo que no pueden ser el primer elemento que es más pequeño y no necesitamos buscarlos. El elemento medio es, por lo tanto, el último lugar posible en el que podría estar.
Tenga en cuenta que en cada iteración eliminamos al menos la mitad de los elementos restantes de la consideración. Si se ejecuta la rama superior, los elementos en el rango [bajo, (bajo + alto) / 2] se descartan, lo que hace que perdamos piso ((bajo + alto) / 2) – bajo + 1 >= (bajo + alto) / 2 – bajo = (alto – bajo) / 2 elementos.
Si se ejecuta la rama inferior, todos los elementos del rango [(bajo + alto) / 2 + 1, alto] se descartan. Esto nos hace perder alto – piso (bajo + alto) / 2 + 1 >= alto – (bajo + alto) / 2 = (alto – bajo) / 2 elementos.
En consecuencia, terminaremos encontrando el primer elemento más pequeño que el objetivo en O(lg n) iteraciones de este proceso. 
 

// C++ program to find first element that
// is strictly smaller than given target.
#include<bits/stdc++.h>
using namespace std;
 
int next(int arr[], int target, int end)
{
      // Minimum size of the array should be 1
      if(end == 0) return -1;
    // If target lies beyond the max element, than the index of strictly smaller
      // value than target should be (end - 1)
      if (target > arr[end - 1]) return end-1;
   
    int start = 0;
 
    int ans = -1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
 
        // Move to the left side if the target is smaller
        if (arr[mid] >= target)
        {
            end = mid - 1;
        }
 
        // Move right side
        else
        {
            ans = mid;
            start = mid + 1;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 5, 8, 12 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << (next(arr, 5, n));
    return 0;
}
 
// This code is contributed by d-dalal

// Java program to find first element that
// is strictly smaller than given target.
   
class GfG {
   
    private static int next(int[] arr, int target)
    {
           
        int start = 0, end = arr.length-1;
          // Minimum size of the array should be 1
        if(end == 0) return -1;
        // If target lies beyond the max element, than the index of strictly smaller
        // value than target should be (end - 1)
        if (target > arr[end]) return end;
   
        int ans = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
   
            // Move to the left side if the target is smaller
            if (arr[mid] >= target) {
                end = mid - 1;
            }
   
            // Move right side
            else {
                ans = mid;
                start = mid + 1;
            }
        }
        return ans;
    }
   
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5, 8, 12 };
        System.out.println(next(arr, 5));
    }
}

# Python3 program to find first element that
# is strictly smaller than given target
 
 
def next(arr, target):
    start = 0;
    end = len(arr) - 1;
    # Minimum size of the array should be 1
    if (end == 0):
        return -1;
    '''
    If target lies beyond the max element, than the index of strictly smaller
    value than target should be (end - 1)
    '''
    if (target > arr[end]):
        return end;
   
    ans = -1;
    while (start <= end):
        mid = (start + end) // 2;
   
        # Move to the left side if target is
        # smaller
        if (arr[mid] >= target):
            end = mid - 1;
   
        # Move right side
        else:
            ans = mid;
            start = mid + 1;
 
    return ans;
   
# Driver code
if __name__ == '__main__':
 
    arr = [ 1, 2, 3, 5, 8, 12 ];
    print(next(arr, 5));
   
# This code is contributed by d-dalal

// C# program to find first element that
// is strictly smaller than given target.
using System;
class GfG {
 
    private static int next(int[] arr, int target)
    {
        int start = 0, end = arr.Length-1;
          // Minimum size of the array should be 1
        if(end == 0) return -1;
        // If target lies beyond the max element, than the index of strictly smaller
        // value than target should be (end - 1)
        if (target > arr[end]) return end;
 
        int ans = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
 
            // Move to the left side if the target is smaller
            if (arr[mid] >= target) {
                end = mid - 1;
            }
 
            // Move right side
            else {
                ans = mid;
                start = mid + 1;
            }
        }
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 5, 8, 12 };
        Console.WriteLine(next(arr, 5));
    }
}
 
// This code is contributed by d-dalal.

<?php
// PHP program to find first element that
// is strictly smaller than given target.
    function next0($arr, $target)
    {
        $start = 0; $end = sizeof($arr)-1;
           
          // Minimum size of the array should be 1
        if($end == 0) return -1;
        // If target lies beyond the max element, than the index of strictly smaller
        // value than target should be (end - 1)
        if ($target > $arr[$end]) return $end;
 
        $ans = -1;
        while ($start <= $end)
        {
            $mid =(int)(($start + $end) / 2);
 
            // Move to the left side if the target is smaller
            if ($arr[$mid] >= $target)
            {
                $end = $mid - 1;
            }
 
            // Move right side
            else
            {
                $ans = $mid;
                $start = $mid + 1;
            }
        }
        return $ans;
    }
 
    // Driver code
    {
        $arr = array(1, 2, 3, 5, 8, 12 );
        echo(next0($arr, 5));
    }
 
// This code is contributed by d-dalal.

2