Cuente elementos menores o iguales a un valor dado en una array rotada ordenada

Dada una array ordenada de n enteros distintos rotados en algún punto. Dado un valor x . El problema es contar todos los elementos de la array que son menores o iguales que x .

Ejemplos: 

Input : arr[] = {4, 5, 8, 1, 3}, 
            x = 6
Output : 4

Input : arr[] = {6, 10, 12, 15, 2, 4, 5}, 
            x = 14
Output : 6

Enfoque ingenuo: uno por uno, recorra todos los elementos de la array y cuente los que son menores o iguales que x . Tiempo Complejidad O(n).

Enfoque eficiente: requisito previo de una búsqueda binaria modificada que puede devolver el índice del elemento más grande menor o igual a un valor dado en un rango ordenado de arr[l…h] . 

Consulte esta publicación para la búsqueda binaria modificada requerida:

Pasos:

1. Encuentre el índice del elemento más pequeño en una array ordenada rotada. Consulte esta publicación. Que sea min_index .
2. Si x <= arr[n-1] , busque el índice del elemento más grande menor o igual que x en el rango ordenado arr[min_index…n-1] con la ayuda de la búsqueda binaria modificada. 
   Sea index1 . Ahora, cuenta = index1 + 1 – min_index.
3. Si 0 <= (min_index -1) && x <= arr[min_index – 1] , busque el índice del elemento más grande menor o igual que x en el rango ordenado arr[0…min_index-1] con la ayuda de modificado búsqueda binaria. Que sea index2 . Ahora, cuenta = n – min_index + index2 + 1.
4. De lo contrario cuenta = n.

// C++ implementation to count elements less than or
// equal to a given value in a sorted rotated array
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the minimum element's index
int findMinIndex(int arr[], int low, int high)
{
    // This condition is needed to handle the case when
    // array is not rotated at all
    if (high < low)  return 0;
  
    // If there is only one element left
    if (high == low) return low;
  
    // Find mid
    int mid = (low + high) / 2;
  
    // Check if element (mid+1) is minimum element. Consider
    // the cases like {3, 4, 5, 1, 2}
    if (mid < high && arr[mid+1] < arr[mid])
       return (mid + 1);
  
    // Check if mid itself is minimum element
    if (mid > low && arr[mid] < arr[mid - 1])
       return mid;
  
    // Decide whether we need to go to left half or right half
    if (arr[high] > arr[mid])
       return findMinIndex(arr, low, mid-1);
    return findMinIndex(arr, mid+1, high);
}
 
// function returns the index of largest element
// smaller than equal to 'x' in 'arr[l...h]'.
// If no such element exits in the given range,
// then it returns l-1.
int binary_search(int arr[], int l, int h, int x)
{
    while (l <= h)
    {
        int mid = (l+h) / 2;
 
        // if 'x' is less than or equal to arr[mid],
        // then search in arr[mid+1...h]
        if (arr[mid] <= x)
            l = mid + 1;
 
        // else search in arr[l...mid-1]   
        else
            h = mid - 1;   
    }
     
    // required index
    return h;
}
 
// function to count elements less than
// or equal to a given value
int countEleLessThanOrEqual(int arr[], int n, int x)
{
    // index of the smallest element in the array
    int min_index = findMinIndex(arr, 0, n-1);
     
    // if largest element smaller than or equal to 'x' lies
    // in the sorted range arr[min_index...n-1]
    if (x <= arr[n-1])
        return (binary_search(arr, min_index, n-1, x) + 1 - min_index);
     
    // if largest element smaller than or equal to 'x' lies
    // in the sorted range arr[0...min_index-1]
    if ((min_index - 1) >= 0 && x <= arr[min_index - 1])
        return (n - min_index + binary_search(arr, 0, min_index-1, x) + 1);
     
    // else all the elements of the array
    // are less than 'x'   
    return n;               
}
 
// Driver program to test above
int main()
{
    int arr[] = {6, 10, 12, 15, 2, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 14;
    cout << "Count = "
         << countEleLessThanOrEqual(arr, n, x);
    return 0;
}

// Java implementation to count elements
// less than or equal to a given
// value in a sorted rotated array
 
class GFG {
     
// function to find the minimum
// element's index
static int findMinIndex(int arr[], int low, int high)
{
    // This condition is needed to handle
    // the case when array is not rotated at all
    if (high < low)
    return 0;
 
    // If there is only one element left
    if (high == low)
    return low;
 
    // Find mid
    int mid = (low + high) / 2;
 
    // Check if element (mid+1) is
    // minimum element. Consider
    // the cases like {3, 4, 5, 1, 2}
    if (mid < high && arr[mid + 1] < arr[mid])
    return (mid + 1);
 
    // Check if mid itself is minimum element
    if (mid > low && arr[mid] < arr[mid - 1])
    return mid;
 
    // Decide whether we need to go to
    // left half or right half
    if (arr[high] > arr[mid])
    return findMinIndex(arr, low, mid - 1);
    return findMinIndex(arr, mid + 1, high);
}
 
// function returns the index of largest element
// smaller than equal to 'x' in 'arr[l...h]'.
// If no such element exits in the given range,
// then it returns l-1.
static int binary_search(int arr[], int l, int h, int x)
{
    while (l <= h) {
    int mid = (l + h) / 2;
 
    // if 'x' is less than or equal to arr[mid],
    // then search in arr[mid+1...h]
    if (arr[mid] <= x)
        l = mid + 1;
 
    // else search in arr[l...mid-1]
    else
        h = mid - 1;
    }
 
    // required index
    return h;
}
 
// function to count elements less than
// or equal to a given value
static int countEleLessThanOrEqual(int arr[], int n, int x)
{
    // index of the smallest element in the array
    int min_index = findMinIndex(arr, 0, n - 1);
 
    // if largest element smaller than or
    // equal to 'x' lies in the sorted
    // range arr[min_index...n-1]
    if (x <= arr[n - 1])
    return (binary_search(arr, min_index, n - 1, x) + 1 - min_index);
 
    // if largest element smaller than or
    // equal to 'x' lies in the sorted
    // range arr[0...min_index-1]
    if ((min_index - 1) >= 0 && x <= arr[min_index - 1])
    return (n - min_index + binary_search(arr, 0, min_index - 1, x) + 1);
 
    // else all the elements of the array
    // are less than 'x'
    return n;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = {6, 10, 12, 15, 2, 4, 5};
    int n = arr.length;
    int x = 14;
    System.out.print("Count = " +
                      countEleLessThanOrEqual(arr, n, x));
}
}
 
// This code is contributed by Anant Agarwal.

# Python implementation to
# count elements less than or
# equal to a given value
# in a sorted rotated array
 
# function to find the
# minimum element's index
def findMinIndex(arr,low,high):
 
    # This condition is needed
    # to handle the case when
    # array is not rotated at all
    if (high < low):
        return 0
   
    # If there is only one element left
    if (high == low):
        return low
   
    # Find mid
    mid = (low + high) // 2
   
    # Check if element (mid+1) is
    # minimum element. Consider
    # the cases like {3, 4, 5, 1, 2}
    if (mid < high and arr[mid+1] < arr[mid]):
       return (mid + 1)
   
    # Check if mid itself
    # is minimum element
    if (mid > low and arr[mid] < arr[mid - 1]):
       return mid
   
    # Decide whether we need to
    # go to left half or right half
    if (arr[high] > arr[mid]):
       return findMinIndex(arr, low, mid-1)
    return findMinIndex(arr, mid+1, high)
 
# function returns the
# index of largest element
# smaller than equal to
# 'x' in 'arr[l...h]'.
# If no such element exits
# in the given range,
# then it returns l-1.
def binary_search(arr,l,h,x):
 
    while (l <= h):
     
        mid = (l+h) // 2
  
        # if 'x' is less than
        # or equal to arr[mid],
        # then search in arr[mid+1...h]
        if (arr[mid] <= x):
            l = mid + 1
  
        # else search in arr[l...mid-1]   
        else:
            h = mid - 1   
     
    # required index
    return h
  
# function to count
# elements less than
# or equal to a given value
def countEleLessThanOrEqual(arr,n,x):
 
    # index of the smallest
    # element in the array
    min_index = findMinIndex(arr, 0, n-1)
      
    # if largest element smaller
    # than or equal to 'x' lies
    # in the sorted range arr[min_index...n-1]
    if (x <= arr[n-1]):
        return (binary_search(arr, min_index, n-1, x) + 1 - min_index)
      
    # if largest element smaller
    # than or equal to 'x' lies
    # in the sorted range arr[0...min_index-1]
    if ((min_index - 1) >= 0 and x <= arr[min_index - 1]):
        return (n - min_index + binary_search(arr, 0, min_index-1, x) + 1)
      
    # else all the elements of the array
    # are less than 'x'   
    return n               
 
# driver code
arr = [6, 10, 12, 15, 2, 4, 5]
n = len(arr)
x = 14
 
print("Count = ",end="")
print(countEleLessThanOrEqual(arr, n, x))
 
# This code is contributed
# by Anant Agarwal.

// C# implementation to count elements
// less than or equal to a given
// value in a sorted rotated array
using System;
         
public class GFG {
     
    // function to find the minimum
    // element's index
    static int findMinIndex(int []arr, int low,
                                      int high)
    {
         
        // This condition is needed to handle
        // the case when array is not rotated
        // at all
        if (high < low)
            return 0;
     
        // If there is only one element left
        if (high == low)
            return low;
     
        // Find mid
        int mid = (low + high) / 2;
     
        // Check if element (mid+1) is
        // minimum element. Consider
        // the cases like {3, 4, 5, 1, 2}
        if (mid < high && arr[mid + 1] < arr[mid])
            return (mid + 1);
     
        // Check if mid itself is minimum element
        if (mid > low && arr[mid] < arr[mid - 1])
            return mid;
     
        // Decide whether we need to go to
        // left half or right half
        if (arr[high] > arr[mid])
            return findMinIndex(arr, low, mid - 1);
             
        return findMinIndex(arr, mid + 1, high);
    }
     
    // function returns the index of largest element
    // smaller than equal to 'x' in 'arr[l...h]'.
    // If no such element exits in the given range,
    // then it returns l-1.
    static int binary_search(int []arr, int l,
                                       int h, int x)
    {
        while (l <= h)
        {
            int mid = (l + h) / 2;
         
            // if 'x' is less than or equal to
            // arr[mid], then search in
            // arr[mid+1...h]
            if (arr[mid] <= x)
                l = mid + 1;
         
            // else search in arr[l...mid-1]
            else
                h = mid - 1;
        }
     
        // required index
        return h;
    }
     
    // function to count elements less than
    // or equal to a given value
    static int countEleLessThanOrEqual(int []arr,
                                      int n, int x)
    {
         
        // index of the smallest element in
        // the array
        int min_index = findMinIndex(arr, 0, n - 1);
     
        // if largest element smaller than or
        // equal to 'x' lies in the sorted
        // range arr[min_index...n-1]
        if (x <= arr[n - 1])
            return (binary_search(arr, min_index,
                          n - 1, x) + 1 - min_index);
     
        // if largest element smaller than or
        // equal to 'x' lies in the sorted
        // range arr[0...min_index-1]
        if ((min_index - 1) >= 0 &&
                             x <= arr[min_index - 1])
            return (n - min_index + binary_search(arr,
                             0, min_index - 1, x) + 1);
     
        // else all the elements of the array
        // are less than 'x'
        return n;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = {6, 10, 12, 15, 2, 4, 5};
        int n = arr.Length;
        int x = 14;
         
        Console.Write("Count = " +
                countEleLessThanOrEqual(arr, n, x));
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP implementation to count elements
// less than or equal to a given value
// in a sorted rotated array
 
// function to find the minimum
// element's index
function findMinIndex(&$arr, $low, $high)
{
    // This condition is needed to
    // handle the case when array
    // is not rotated at all
    if ($high < $low) return 0;
 
    // If there is only one element left
    if ($high == $low) return $low;
 
    // Find mid
    $mid = intval(($low + $high) / 2);
 
    // Check if element (mid+1) is
    // minimum element. Consider
    // the cases like {3, 4, 5, 1, 2}
    if ($mid < $high &&
        $arr[$mid + 1] < $arr[$mid])
    return ($mid + 1);
 
    // Check if mid itself is minimum element
    if ($mid > $low &&
        $arr[$mid] < $arr[$mid - 1])
    return $mid;
 
    // Decide whether we need to go
    // to left half or right half
    if ($arr[$high] > $arr[$mid])
    return findMinIndex($arr, $low, $mid - 1);
    return findMinIndex($arr, $mid + 1, $high);
}
 
// function returns the index of largest
// element smaller than equal to 'x' in 
// 'arr[l...h]'. If no such element exits
// in the given range, then it returns l-1.
function binary_search(&$arr, $l, $h, $x)
{
    while ($l <= $h)
    {
        $mid = intval(($l + $h) / 2);
 
        // if 'x' is less than or equal
        // to arr[mid], then search in
        // arr[mid+1...h]
        if ($arr[$mid] <= $x)
            $l = $mid + 1;
 
        // else search in arr[l...mid-1]
        else
            $h = $mid - 1;
    }
     
    // required index
    return $h;
}
 
// function to count elements less
// than or equal to a given value
function countEleLessThanOrEqual(&$arr, $n, $x)
{
    // index of the smallest element
    // in the array
    $min_index = findMinIndex($arr, 0, $n - 1);
     
    // if largest element smaller than
    // or equal to 'x' lies in the sorted
    // range arr[min_index...n-1]
    if ($x <= $arr[$n - 1])
        return (binary_search($arr, $min_index,
                              $n - 1, $x) + 1 - $min_index);
     
    // if largest element smaller than or
    // equal to 'x' lies in the sorted
    // range arr[0...min_index-1]
    if (($min_index - 1) >= 0 &&
         $x <= $arr[$min_index - 1])
        return ($n - $min_index +
                binary_search($arr, 0,
                              $min_index - 1, $x) + 1);
     
    // else all the elements of
    // the array are less than 'x'
    return $n;            
}
 
// Driver Code
$arr = array(6, 10, 12, 15, 2, 4, 5);
$n = sizeof($arr);
$x = 14;
echo "Count = " . countEleLessThanOrEqual($arr, $n, $x);
 
// This code is contributed
// by ChitraNayal
?>

<script>
// Javascript implementation to count elements
// less than or equal to a given
// value in a sorted rotated array
     
    // function to find the minimum
    // element's index
    function findMinIndex(arr,low,high)
    {
        // This condition is needed to handle
    // the case when array is not rotated at all
    if (high < low)
        return 0;
   
    // If there is only one element left
    if (high == low)
        return low;
   
    // Find mid
    let mid = Math.floor((low + high) / 2);
   
    // Check if element (mid+1) is
    // minimum element. Consider
    // the cases like {3, 4, 5, 1, 2}
    if (mid < high && arr[mid + 1] < arr[mid])
        return (mid + 1);
   
    // Check if mid itself is minimum element
    if (mid > low && arr[mid] < arr[mid - 1])
        return mid;
   
    // Decide whether we need to go to
    // left half or right half
    if (arr[high] > arr[mid])
        return findMinIndex(arr, low, mid - 1);
    return findMinIndex(arr, mid + 1, high);
    }
     
    // function returns the index of largest element
// smaller than equal to 'x' in 'arr[l...h]'.
// If no such element exits in the given range,
// then it returns l-1.
    function binary_search(arr,l,h,x)
    {
        while (l <= h) {
    let mid = Math.floor((l + h) / 2);
   
    // if 'x' is less than or equal to arr[mid],
    // then search in arr[mid+1...h]
    if (arr[mid] <= x)
        l = mid + 1;
   
    // else search in arr[l...mid-1]
    else
        h = mid - 1;
    }
   
    // required index
    return h;
    }
     
    // function to count elements less than
// or equal to a given value
    function countEleLessThanOrEqual(arr,n,x)
    {
        // index of the smallest element in the array
    let min_index = findMinIndex(arr, 0, n - 1);
   
    // if largest element smaller than or
    // equal to 'x' lies in the sorted
    // range arr[min_index...n-1]
    if (x <= arr[n - 1])
    return (binary_search(arr, min_index, n - 1, x) + 1 - min_index);
   
    // if largest element smaller than or
    // equal to 'x' lies in the sorted
    // range arr[0...min_index-1]
    if ((min_index - 1) >= 0 && x <= arr[min_index - 1])
        return (n - min_index + binary_search(arr, 0, min_index - 1, x) + 1);
   
    // else all the elements of the array
    // are less than 'x'
    return n;
    }
     
     
    // Driver code
    let arr=[6, 10, 12, 15, 2, 4, 5];
    let n = arr.length;
    let x = 14;
    document.write("Count = " +
                      countEleLessThanOrEqual(arr, n, x));
       
     
    // This code is contributed by rag2127
</script>

Count = 6

Complejidad de tiempo: O (logn)

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.