Рубрики

Потолок в отсортированном массиве

Учитывая отсортированный массив и значение x, потолок x является наименьшим элементом в массиве, большим или равным x, а floor является наибольшим элементом, меньшим или равным x. Предположим, что массив отсортирован в неубывающем порядке. Напишите эффективные функции, чтобы найти пол и потолок х.

Примеры :

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0:    floor doesn't exist in array,  ceil  = 1
For x = 1:    floor  = 1,  ceil  = 1
For x = 5:    floor  = 2,  ceil  = 8
For x = 20:   floor  = 19,  ceil doesn't exist in array

В следующих методах мы реализовали только функции поиска потолка. Поиск этажа может быть реализован таким же образом.

Метод 1 (линейный поиск)
Алгоритм поиска потолка х:
1) Если x меньше или равен первому элементу в массиве, вернуть 0 (индекс первого элемента)
2) Иначе линейно ищите индекс i такой, что x лежит между arr [i] и arr [i + 1].
3) Если мы не найдем индекс i на шаге 2, вернем -1

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для получения индекса потолка x в arr [low..high] * /

int ceilSearch(int arr[], int low, int high, int x) 

      

    int i; 

      

    / * Если x меньше или равен первому элементу,

        затем верните первый элемент * /

    if(x <= arr[low]) 

        return low; 

      

    / * В противном случае, линейно искать значение ceil * /

    for(i = low; i < high; i++) 

    

        if(arr[i] == x) 

        return i; 

      

        / * если x лежит между arr [i] и arr [i + 1], включая

        arr [i + 1], затем вернуть arr [i + 1] * /

        if(arr[i] < x && arr[i+1] >= x) 

        return i+1; 

    }     

      

    / * Если мы достигнем здесь, то х больше, чем последний элемент

        массива, вернуть -1 в этом случае * /

    return -1; 

  

  
/ * Код водителя * /

int main() 

    int arr[] = {1, 2, 8, 10, 10, 12, 19}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    int x = 3; 

    int index = ceilSearch(arr, 0, n-1, x); 

    if(index == -1) 

        cout << "Ceiling of " << x << " doesn't exist in array "

    else

        cout << "ceiling of " << x << " is " << arr[index]; 

      

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include<stdio.h>

  
/ * Функция для получения индекса потолка x в arr [low..high] * /

int ceilSearch(int arr[], int low, int high, int x)

{

  int i;    

  

  / * Если x меньше или равен первому элементу,

    затем верните первый элемент * /

  if(x <= arr[low])

    return low;  

  

  / * В противном случае, линейно искать значение ceil * /

  for(i = low; i < high; i++)

  {

    if(arr[i] == x)

      return i;

  

    / * если x лежит между arr [i] и arr [i + 1], включая

       arr [i + 1], затем вернуть arr [i + 1] * /

    if(arr[i] < x && arr[i+1] >= x)

       return i+1;

  }         

  

  / * Если мы достигнем здесь, то х больше, чем последний элемент

    массива, вернуть -1 в этом случае * /

  return -1;

}

  

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

   int arr[] = {1, 2, 8, 10, 10, 12, 19};

   int n = sizeof(arr)/sizeof(arr[0]);

   int x = 3;

   int index = ceilSearch(arr, 0, n-1, x);

   if(index == -1)

     printf("Ceiling of %d doesn't exist in array ", x);

   else

     printf("ceiling of %d is %d", x, arr[index]);

   getchar();

   return 0;

}

Джава

class Main

{

    / * Функция для получения индекса потолка

       х в обр [низкий .. высокий] * /

    static int ceilSearch(int arr[], int low, int high, int x)

    {

      int i;    

       

      / * Если х меньше или равен первому

         элемент, затем вернуть первый элемент * /

      if(x <= arr[low])

        return low;  

       

      / * В противном случае, линейно искать значение ceil * /

      for(i = low; i < high; i++)

      {

        if(arr[i] == x)

          return i;

       

        / * если x лежит между arr [i] и arr [i + 1]

        включая arr [i + 1], затем вернуть arr [i + 1] * /

        if(arr[i] < x && arr[i+1] >= x)

           return i+1;

      }         

       

      / * Если мы достигнем здесь, то х больше, чем

      последний элемент массива, в этом случае возвращается -1 *

      return -1;

    }

       

       

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main (String[] args)

    {

       int arr[] = {1, 2, 8, 10, 10, 12, 19};

       int n = arr.length;

       int x = 3;

       int index = ceilSearch(arr, 0, n-1, x);

       if(index == -1)

         System.out.println("Ceiling of "+x+" doesn't exist in array");

       else

         System.out.println("ceiling of "+x+" is "+arr[index]);

    }  

}

python3

# Функция для получения индекса потолка x в arr [low..high] * /

def ceilSearch(arr, low, high, x):

  

    # Если х меньше или равен первому элементу,

    # затем вернуть первый элемент * /

    if x <= arr[low]:

        return low

  

    # В противном случае, линейно ищите значение ceil * /

    i = low

    for i in range(high):

        if arr[i] == x:

            return i

  

        # если x лежит между arr [i] и arr [i + 1], включая

        # arr [i + 1], затем вернуть arr [i + 1] * /

        if arr[i] < x and arr[i+1] >= x:

            return i+1

          

    # Если мы достигнем здесь, то х больше, чем последний элемент

    # массива, вернуть -1 в этом случае * /

    return -1

  
# Драйверная программа для проверки вышеуказанных функций * /

arr = [1, 2, 8, 10, 10, 12, 19]

n = len(arr)

x = 3

index = ceilSearch(arr, 0, n-1, x);

  

if index == -1:

    print ("Ceiling of %d doesn't exist in array "% x)

else:

    print ("ceiling of %d is %d"%(x, arr[index]))

  
# Этот код предоставлен Shreyanshi Arun

C #

// C # программа для поиска celing
// в отсортированном массиве

using System;

  

class GFG {

      

    // Функция для получения индекса потолка

    // x в arr [low..high]

    static int ceilSearch(int[] arr, int low, 

                           int high, int x)

    {

        int i;

  

        // Если х меньше или равен

        // к первому элементу, затем возвращаем

        // первый элемент

        if (x <= arr[low])

            return low;

  

        // В противном случае, линейный поиск

        // для значения ceil

        for (i = low; i < high; i++) {

            if (arr[i] == x)

                return i;

  

            / * если x лежит между arr [i] и

            arr [i + 1], включая arr [i + 1],

            затем вернуть arr [i + 1] * /

            if (arr[i] < x && arr[i + 1] >= x)

                return i + 1;

        }

  

        / * Если мы достигнем здесь, то х

        больше, чем последний элемент

        массива, вернуть -1 в

        этот случай */

        return -1;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };

        int n = arr.Length;

        int x = 3;

        int index = ceilSearch(arr, 0, n - 1, x);

          

        if (index == -1)

            Console.Write("Ceiling of " + x +

                     " doesn't exist in array");

        else

            Console.Write("ceiling of " + x +

                         " is " + arr[index]);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// Функция для получения индекса
// потолок x в arr [low..high]

function ceilSearch($arr, $low, $high, $x)

{

  

    // Если х меньше или равен

    // к первому элементу, затем возвращаем

    // первый элемент

    if($x <= $arr[$low])

        return $low

      

    // В противном случае, линейный поиск

    // для значения ceil

    for($i = $low; $i < $high; $i++)

    {

        if($arr[$i] == $x)

            return $i;

      

        // если x лежит между arr [i] и

        // arr [i + 1], включая arr [i + 1],

        // затем возвращаем arr [i + 1]

        if($arr[$i] < $x && 

           $arr[$i + 1] >= $x)

            return $i + 1;

    }     

      

    // Если мы достигнем здесь, то х больше

    // чем последний элемент массива,

    // вернуть -1 в этом случае

    return -1;

}

  
// Код драйвера

$arr = array(1, 2, 8, 10, 10, 12, 19);

$n = sizeof($arr);

$x = 3;

$index = ceilSearch($arr, 0, $n - 1, $x);

if($index == -1)

    echo("Ceiling of " . $x

         " doesn't exist in array ");

else

    echo("ceiling of " . $x . " is "

                        $arr[$index]);

  
// Этот код предоставлен Ajit.
?>


Выход :

ceiling of 3 is 8

Сложность времени: O (n)

Метод 2 (бинарный поиск)
Вместо использования линейного поиска, здесь используется бинарный поиск для определения индекса. Бинарный поиск уменьшает сложность времени до O (Logn).

C ++

#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для получения индекса

   потолок х в обр [низкий .. высокий] * /

int ceilSearch(int arr[], int low, int high, int x) 

    int mid;     

      

    / * Если х меньше чем

       или равен первому элементу,

       затем верните первый элемент * /

    if(x <= arr[low]) 

        return low; 

      

    / * Если х больше, чем последний элемент,

       затем верните -1 * /

    if(x > arr[high]) 

        return -1; 

      

    / * получить индекс среднего элемента arr [low..high] * /

    mid = (low + high) / 2; / * низкий + (высокий - низкий) / 2 * /

      

    / * Если х совпадает со средним элементом,

       затем вернитесь в середину * /

    if(arr[mid] == x) 

        return mid; 

          

    / * Если x больше, чем arr [mid],

       тогда либо arr [mid + 1] будет потолком x

       или потолок лежит в обр [средняя + 1 ... высокая] * /

    else if(arr[mid] < x) 

    

        if(mid + 1 <= high && x <= arr[mid + 1]) 

            return mid + 1; 

        else

            return ceilSearch(arr, mid + 1, high, x); 

    

      

    / * Если x меньше, чем arr [mid],

       тогда либо обр [середина] является потолком х

       или потолок лежит в обр [средняя-1 ... высокая] * /

    else

    

        if(mid - 1 >= low && x > arr[mid - 1]) 

            return mid; 

        else

            return ceilSearch(arr, low, mid - 1, x); 

    

  
// Код драйвера

int main() 

    int arr[] = {1, 2, 8, 10, 10, 12, 19}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    int x = 20; 

    int index = ceilSearch(arr, 0, n-1, x); 

    if(index == -1) 

        cout << "Ceiling of " << x 

             << " doesn't exist in array "

    else

        cout << "ceiling of " << x 

             << " is " << arr[index]; 

      

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>

  
/ * Функция для получения индекса потолка x в arr [low..high] * /

int ceilSearch(int arr[], int low, int high, int x)

{

  int mid;    

  

  / * Если x меньше или равен первому элементу,

    затем верните первый элемент * /

  if(x <= arr[low])

    return low; 

  

  / * Если x больше, чем последний элемент, вернуть -1 * /

  if(x > arr[high])

    return -1;  

  

  / * получить индекс среднего элемента arr [low..high] * /

  mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2 * /

  

  / * Если x совпадает со средним элементом, вернуть mid * /

  if(arr[mid] == x)

    return mid;

      

  / * Если x больше, чем arr [mid], то либо arr [mid + 1]

    потолок x или потолок в arr [mid + 1 ... high] * /  

  else if(arr[mid] < x)

  {

    if(mid + 1 <= high && x <= arr[mid+1])

      return mid + 1;

    else 

      return ceilSearch(arr, mid+1, high, x);

  }

  

  / * Если x меньше arr [mid], то либо arr [mid]

     потолок x или потолок в arr [mid-1 ... high] * /    

  else

  {

    if(mid - 1 >= low && x > arr[mid-1])

      return mid;

    else     

      return ceilSearch(arr, low, mid - 1, x);

  }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

   int arr[] = {1, 2, 8, 10, 10, 12, 19};

   int n = sizeof(arr)/sizeof(arr[0]);

   int x = 20;

   int index = ceilSearch(arr, 0, n-1, x);

   if(index == -1)

     printf("Ceiling of %d doesn't exist in array ", x);

   else  

     printf("ceiling of %d is %d", x, arr[index]);

   getchar();

   return 0;

}

Джава

class Main

{

    / * Функция для получения индекса

       потолок х в обр [низкий .. высокий] * /

    static int ceilSearch(int arr[], int low, int high, int x)

    {

      int mid;    

        

      / * Если х меньше или равен

         первый элемент, затем вернуть первый элемент * /

      if(x <= arr[low])

        return low; 

       

      / * Если х больше чем последний

         элемент, затем вернуть -1 * /

      if(x > arr[high])

        return -1;  

       

      / * получить индекс среднего элемента

         обр [низкий .. высокий] * /

      mid = (low + high)/2/ * низкий + (высокий - низкий) / 2 * /

       

      / * Если х совпадает со средним элементом,

         затем вернитесь в середину * /

      if(arr[mid] == x)

        return mid;

           

      / * Если x больше, чем arr [mid], то

         либо arr [mid + 1] является потолком x, либо

         потолок лежит в обр [средняя + 1 ... высокая] * / 

      else if(arr[mid] < x)

      {

        if(mid + 1 <= high && x <= arr[mid+1])

          return mid + 1;

        else

          return ceilSearch(arr, mid+1, high, x);

      }

       

      / * Если x меньше, чем arr [mid],

         тогда либо обр [середина] является потолком х

         или потолок лежит в обр [средняя-1 ... высокая] * /   

      else

      {

        if(mid - 1 >= low && x > arr[mid-1])

          return mid;

        else    

          return ceilSearch(arr, low, mid - 1, x);

      }

    }

       

       

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main (String[] args)

    {

       int arr[] = {1, 2, 8, 10, 10, 12, 19};

       int n = arr.length;

       int x = 8;

       int index = ceilSearch(arr, 0, n-1, x);

       if(index == -1)

         System.out.println("Ceiling of "+x+" doesn't exist in array");

       else 

         System.out.println("ceiling of "+x+" is "+arr[index]);

    }  

}

python3

# Функция для получения индекса потолка x в arr [low..high] * /

def ceilSearch(arr, low, high, x):

  

    # Если х меньше или равен первому элементу,

    # затем вернуть первый элемент * /

    if x <= arr[low]:

        return low 

  

    # Если x больше, чем последний элемент, вернуть -1 * /

    if x > arr[high]:

        return -1  

   

    # получить индекс среднего элемента arr [low..high] * /

    mid = (low + high)/2# низкий + (высокий - низкий) / 2 * /

   

    # Если x совпадает со средним элементом, вернуть mid * /

    if arr[mid] == x:

        return mid

  

    # Если x больше, чем arr [mid], то либо arr [mid + 1]

    # потолок x или потолок в arr [mid + 1 ... high] * /

    elif arr[mid] < x:

        if mid + 1 <= high and x <= arr[mid+1]:

            return mid + 1

        else:

            return ceilSearch(arr, mid+1, high, x)

   

    # Если x меньше, чем arr [mid], то либо arr [mid]

    # потолок x или потолок в arr [mid-1 ... high] * /

    else:

        if mid - 1 >= low and x > arr[mid-1]:

            return mid

        else:

            return ceilSearch(arr, low, mid - 1, x)

   
# Драйверная программа для проверки вышеуказанных функций * /

arr = [1, 2, 8, 10, 10, 12, 19]

n = len(arr)

x = 20

index = ceilSearch(arr, 0, n-1, x);

  

if index == -1:

    print ("Ceiling of %d doesn't exist in array "% x)

else:

    print ("ceiling of %d is %d"%(x, arr[index]))

  
# Этот код предоставлен Shreyanshi Arun

C #

// C # программа для поиска celing
// в отсортированном массиве

using System;

  

class GFG {

      

    // Функция для получения индекса потолка

    // x в arr [low..high]

    static int ceilSearch(int[] arr, int low, 

                             int high, int x)

    {

        int mid;

  

        // Если х меньше или равен

        // к первому элементу, затем

        // вернуть первый элемент.

        if (x <= arr[low])

            return low;

  

        // Если х больше чем последний

        // элемент, затем вернуть -1

        if (x > arr[high])

            return -1;

  

        // получаем индекс середины

        // элемент arr [low..high]

        mid = (low + high) / 2; 

        // низкий + (высокий - низкий) / 2

  

        // Если х совпадает со средним

        // элемент затем возвращает середину

        if (arr[mid] == x)

            return mid;

  

        // Если x больше, чем arr [mid],

        // тогда либо arr [mid + 1]

        // потолок х или потолок лжи

        // в обр [средняя + 1 ... высокая]

        else if (arr[mid] < x) {

            if (mid + 1 <= high && x <= arr[mid + 1])

                return mid + 1;

            else

                return ceilSearch(arr, mid + 1, high, x);

        }

  

        // Если x меньше, чем arr [mid],

        // тогда либо arr [mid] является потолком

        // х или потолок лежит в

        // arr [mid-1 ... high]

        else {

            if (mid - 1 >= low && x > arr[mid - 1])

                return mid;

            else

                return ceilSearch(arr, low, mid - 1, x);

        }

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 1, 2, 8, 10, 10, 12, 19 };

        int n = arr.Length;

        int x = 8;

        int index = ceilSearch(arr, 0, n - 1, x);

        if (index == -1)

            Console.Write("Ceiling of " + x +

                      " doesn't exist in array");

        else

            Console.Write("ceiling of " + x + 

                            " is " + arr[index]);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для потолка в
// отсортированный массив

  
// Функция для получения индекса потолка
// x в arr [low..high]

function ceilSearch($arr, $low

                    $high, $x)

{

    $mid

      

    / * Если х меньше или

       равен первому элементу,

       затем верните первый элемент * /

    if($x <= $arr[$low])

        return $low

      

    / * Если х больше чем

       последний элемент, затем возврат

       -1 * /

    if($x > $arr[$high])

        return -1; 

      

    / * получить индекс среднего

       элемент arr [low..high] * /

    // низкий + (высокий - низкий) / 2

    $mid = ($low + $high)/2; 

      

    / * Если х совпадает со средним элементом,

       затем вернитесь в середину * /

    if($arr[$mid] == $x)

        return $mid;

          

    / * Если x больше, чем arr [mid],

       тогда либо arr [mid + 1]

       потолок х или потолок лежит

       в обр [средняя + 1 ... высокая] * /

    else if($arr[$mid] < $x)

    {

        if($mid + 1 <= $high && 

           $x <= $arr[$mid + 1])

            return $mid + 1;

        else

            return ceilSearch($arr, $mid + 1, 

                              $high, $x);

    }

      

    / * Если x меньше, чем arr [mid],

       тогда либо arr [mid] является потолком

       х или потолок лежит в

       обр [середина 1 ... высокая] * /

    else

    {

        if($mid - 1 >= $low && 

           $x > $arr[$mid - 1])

            return $mid;

        else

         return ceilSearch($arr, $low

                           $mid - 1, $x);

    }

}

  
// Код драйвера

$arr = array(1, 2, 8, 10, 10, 12, 19);

$n = sizeof($arr);

$x = 20;

$index = ceilSearch($arr, 0, $n - 1, $x);

if($index == -1)

    echo("Ceiling of $x doesn't exist in array ");

else

    echo("ceiling of $x is"); 

    echo(isset($arr[$index]));

  
// Этот код предоставлен нитин митталь.
?>


Выход :

Ceiling of 20 doesn't exist in array 

Сложность времени: O (Logn)

Статьи по Теме:
Этаж в отсортированном массиве
Найти пол и потолок в несортированном массиве

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете более эффективные способы решения той же проблемы или хотите поделиться кодом для реализации на уровне.

Рекомендуемые посты:

Потолок в отсортированном массиве

0.00 (0%) 0 votes