Рубрики

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

В этом посте поиск, вставка и удаление операции в отсортированном массиве обсуждается.

Операция поиска

В отсортированном массиве операция поиска может быть выполнена с использованием бинарного поиска .

C ++

// C ++ программа для реализации бинарного поиска в отсортированном массиве
#include <iostream>

using namespace std;

  

int binarySearch(int arr[], int low, int high, int key)

{

    if (high < low)

        return -1;

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

    if (key == arr[mid])

        return mid;

    if (key > arr[mid])

        return binarySearch(arr, (mid + 1), high, key);

    return binarySearch(arr, low, (mid - 1), key);

}

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

int main()

{

    // Давайте искать 3 в массиве ниже

    int arr[] = { 5, 6, 7, 8, 9, 10 };

    int n, key;

  

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

    key = 10;

  

    cout << "Index: " << binarySearch(arr, 0, n, key) << endl;

    return 0;

}

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

С

// C программа для реализации бинарного поиска в отсортированном массиве
#include <stdio.h>

  

int binarySearch(int arr[], int low, int high, int key)

{

    if (high < low)

        return -1;

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

    if (key == arr[mid])

        return mid;

    if (key > arr[mid])

        return binarySearch(arr, (mid + 1), high, key);

    return binarySearch(arr, low, (mid - 1), key);

}

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

int main()

{

    // Давайте искать 3 в массиве ниже

    int arr[] = { 5, 6, 7, 8, 9, 10 };

    int n, key;

  

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

    key = 10;

  

    printf("Index: %d\n", binarySearch(arr, 0, n, key));

    return 0;

}

Джава

// Java-программа для реализации бинарного
// поиск в отсортированном массиве

  

class Main {

    // функция для реализации

    // бинарный поиск

    static int binarySearch(int arr[], int low, int high, int key)

    {

        if (high < low)

            return -1;

  

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

        int mid = (low + high) / 2;

        if (key == arr[mid])

            return mid;

        if (key > arr[mid])

            return binarySearch(arr, (mid + 1), high, key);

        return binarySearch(arr, low, (mid - 1), key);

    }

  

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

    public static void main(String[] args)

    {

        int arr[] = { 5, 6, 7, 8, 9, 10 };

        int n, key;

        n = arr.length;

        key = 10;

  

        System.out.println("Index: " + binarySearch(arr, 0, n, key));

    }

}

python3

# Python 3 программа для реализации
# бинарный поиск в отсортированном массиве

  

def binarySearch(arr, low, high, key):

  

    if (high < low):

        return -1

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

    mid = (low + high)/2

  

    if (key == arr[int(mid)]):

        return mid

  

    if (key > arr[int(mid)]):

        return binarySearch(arr,

           (mid + 1), high, key)

  

    return (binarySearch(arr, low,

           (mid -1), key))

  
# Драйвер программы для проверки вышеуказанных функций
# Давайте искать 3 в массиве ниже

arr = [5, 6, 7, 8, 9, 10]

n = len(arr)

key = 10

print("Index:", int(binarySearch(arr, 0, n, key) ))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

using System;

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

  

public class GFG {

    // функция для реализации

    // бинарный поиск

    public static int binarySearch(int[] arr, int low, int high, int key)

    {

        if (high < low) {

            return -1;

        }

  

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

        int mid = (low + high) / 2;

        if (key == arr[mid]) {

            return mid;

        }

        if (key > arr[mid]) {

            return binarySearch(arr, (mid + 1), high, key);

        }

        return binarySearch(arr, low, (mid - 1), key);

    }

  

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

    public static void Main(string[] args)

    {

        int[] arr = new int[] { 5, 6, 7, 8, 9, 10 };

        int n, key;

        n = arr.Length;

        key = 10;

  

        Console.WriteLine("Index: " + binarySearch(arr, 0, n, key));

    }

}

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

PHP

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

  

function binarySearch($arr, $low

                      $high, $key

{

    if ($high < $low

    return -1;

      

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

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

      

    if ($key == $arr[(int)$mid])

        return $mid;

      

    if ($key > $arr[(int)$mid]) 

        return binarySearch($arr, ($mid + 1), 

                            $high, $key);

      

    return (binarySearch($arr, $low

                        ($mid -1), $key));

}

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

  
// Давайте искать 3 в массиве ниже

$arr = array(5, 6, 7, 8, 9, 10);

$n = count($arr);

$key = 10;

echo "Index: ", (int)binarySearch($arr, 0, 

                                  $n, $key);

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


Выход:

Index: 5

Операция вставки

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

С

// C программа для реализации операции вставки в
// отсортированный массив.
#include <stdio.h>

  
// Вставляет ключ в arr [] заданной емкости. n является текущим
// размер обр []. Эта функция возвращает n + 1, если вставка
// успешно, иначе n.

int insertSorted(int arr[], int n, int key, int capacity)

{

    // Невозможно вставить больше элементов, если n уже

    // больше или равно capcity

    if (n >= capacity)

        return n;

  

    int i;

    for (i = n - 1; (i >= 0 && arr[i] > key); i--)

        arr[i + 1] = arr[i];

  

    arr[i + 1] = key;

  

    return (n + 1);

}

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

int main()

{

    int arr[20] = { 12, 16, 20, 40, 50, 70 };

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

    int n = 6;

    int i, key = 26;

  

    printf("\nBefore Insertion: ");

    for (i = 0; i < n; i++)

        printf("%d  ", arr[i]);

  

    // Вставка ключа

    n = insertSorted(arr, n, key, capacity);

  

    printf("\nAfter Insertion: ");

    for (i = 0; i < n; i++)

        printf("%d  ", arr[i]);

  

    return 0;

}

Джава

// Java-программа для вставки
// элемент в отсортированном массиве

  

class Main {

    // Вставляет ключ в arr [] данного

    // вместимость. n - текущий размер arr [].

    // Эта функция возвращает n + 1, если вставка

    // успешно, иначе n.

    static int insertSorted(int arr[], int n, int key, int capacity)

    {

        // Невозможно вставить больше элементов, если n уже

        // больше или равно capcity

        if (n >= capacity)

            return n;

  

        int i;

        for (i = n - 1; (i >= 0 && arr[i] > key); i--)

            arr[i + 1] = arr[i];

  

        arr[i + 1] = key;

  

        return (n + 1);

    }

  

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

    public static void main(String[] args)

    {

        int arr[] = new int[20];

        arr[0] = 12;

        arr[1] = 16;

        arr[2] = 20;

        arr[3] = 40;

        arr[4] = 50;

        arr[5] = 70;

        int capacity = arr.length;

        int n = 6;

        int key = 26;

  

        System.out.print("\nBefore Insertion: ");

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

  

        // Вставка ключа

        n = insertSorted(arr, n, key, capacity);

  

        System.out.print("\nAfter Insertion: ");

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

}

python3

# Python3 программа для реализации вставки
# операция в отсортированном массиве.

  
# Вставляет ключ в arr [] заданной емкости.
# n - текущий размер arr []. Эта функция
# возвращает n + 1, если вставка прошла успешно, иначе n.

def insertSorted(arr, n, key, capacity):

      

    # Невозможно вставить больше элементов, если n

    # уже больше или равно пропускной способности

    if (n >= capacity):

        return n

  

    i = n - 1

    while i >= 0 and arr[i] > key:

        arr[i + 1] = arr[i]

        i -= 1

  

    arr[i + 1] = key

  

    return (n + 1)

  
Код водителя

arr = [12, 16, 20, 40, 50, 70]

  

for i in range(20):

    arr.append(0)

  

capacity = len(arr)

n = 6

key = 26

  

print("Before Insertion: ", end = " ");

for i in range(n):

    print(arr[i], end = " ")

      
# Вставка ключа

n = insertSorted(arr, n, key, capacity)

  

print("\nAfter Insertion: ", end = "")

for i in range(n):

    print(arr[i], end = " ")

  
# Этот код предоставлен Мохитом Кумаром

C #

using System;

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

  

public class GFG {

    // Вставляет ключ в arr [] данного

    // вместимость. n - текущий размер arr [].

    // Эта функция возвращает n + 1, если вставка

    // успешно, иначе n.

    public static int insertSorted(int[] arr, int n, int key, int capacity)

    {

        // Невозможно вставить больше элементов, если n уже

        // больше или равно capcity

        if (n >= capacity) {

            return n;

        }

  

        int i;

        for (i = n - 1; (i >= 0 && arr[i] > key); i--) {

            arr[i + 1] = arr[i];

        }

  

        arr[i + 1] = key;

  

        return (n + 1);

    }

  

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

    public static void Main(string[] args)

    {

        int[] arr = new int[20];

        arr[0] = 12;

        arr[1] = 16;

        arr[2] = 20;

        arr[3] = 40;

        arr[4] = 50;

        arr[5] = 70;

        int capacity = arr.Length;

        int n = 6;

        int key = 26;

  

        Console.Write("\nBefore Insertion: ");

        for (int i = 0; i < n; i++) {

            Console.Write(arr[i] + " ");

        }

  

        // Вставка ключа

        n = insertSorted(arr, n, key, capacity);

  

        Console.Write("\nAfter Insertion: ");

        for (int i = 0; i < n; i++) {

            Console.Write(arr[i] + " ");

        }

    }

}

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


Выход:

Before Insertion: 12 16 20 40 50 70 
After Insertion: 12 16 20 26 40 50 70 

Удалить операцию

В операции удаления, элемент, который должен быть удален, ищется с использованием двоичного поиска, а затем выполняется операция удаления с последующим смещением элементов.

С

// C программа для реализации операции удаления в
// отсортированный массив
#include <stdio.h>

  
// Искать лей, который нужно удалить

int binarySearch(int arr[], int low, int high, int key);

  
/ * Функция для удаления элемента * /

int deleteElement(int arr[], int n, int key)

{

    // Находим позицию удаляемого элемента

    int pos = binarySearch(arr, 0, n - 1, key);

  

    if (pos == -1) {

        printf("Element not found");

        return n;

    }

  

    // Удаление элемента

    int i;

    for (i = pos; i < n - 1; i++)

        arr[i] = arr[i + 1];

  

    return n - 1;

}

  

int binarySearch(int arr[], int low, int high, int key)

{

    if (high < low)

        return -1;

    int mid = (low + high) / 2;

    if (key == arr[mid])

        return mid;

    if (key > arr[mid])

        return binarySearch(arr, (mid + 1), high, key);

    return binarySearch(arr, low, (mid - 1), key);

}

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

int main()

{

    int i;

    int arr[] = { 10, 20, 30, 40, 50 };

  

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

    int key = 30;

  

    printf("Array before deletion\n");

    for (i = 0; i < n; i++)

        printf("%d  ", arr[i]);

  

    n = deleteElement(arr, n, key);

  

    printf("\n\nArray after deletion\n");

    for (i = 0; i < n; i++)

        printf("%d  ", arr[i]);

}

Джава

// Java программа для удаления
// элемент из отсортированного массива

  

class Main {

    // бинарный поиск

    static int binarySearch(int arr[], int low, int high, int key)

    {

        if (high < low)

            return -1;

        int mid = (low + high) / 2;

        if (key == arr[mid])

            return mid;

        if (key > arr[mid])

            return binarySearch(arr, (mid + 1), high, key);

        return binarySearch(arr, low, (mid - 1), key);

    }

  

    / * Функция для удаления элемента * /

    static int deleteElement(int arr[], int n, int key)

    {

        // Находим позицию удаляемого элемента

        int pos = binarySearch(arr, 0, n - 1, key);

  

        if (pos == -1) {

            System.out.println("Element not found");

            return n;

        }

  

        // Удаление элемента

        int i;

        for (i = pos; i < n - 1; i++)

            arr[i] = arr[i + 1];

  

        return n - 1;

    }

  

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

    public static void main(String[] args)

    {

  

        int i;

        int arr[] = { 10, 20, 30, 40, 50 };

  

        int n = arr.length;

        int key = 30;

  

        System.out.print("Array before deletion:\n");

        for (i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

  

        n = deleteElement(arr, n, key);

  

        System.out.print("\n\nArray after deletion:\n");

        for (i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

}

C #

// C # программа для удаления
// элемент из отсортированного массива

using System;

public class GFG {

    // бинарный поиск

    static int binarySearch(int[] arr, int low, int high, int key)

    {

        if (high < low)

            return -1;

        int mid = (low + high) / 2;

        if (key == arr[mid])

            return mid;

        if (key > arr[mid])

            return binarySearch(arr, (mid + 1), high, key);

        return binarySearch(arr, low, (mid - 1), key);

    }

  

    / * Функция для удаления элемента * /

    static int deleteElement(int[] arr, int n, int key)

    {

        // Находим позицию удаляемого элемента

        int pos = binarySearch(arr, 0, n - 1, key);

  

        if (pos == -1) {

            Console.WriteLine("Element not found");

            return n;

        }

  

        // Удаление элемента

        int i;

        for (i = pos; i < n - 1; i++)

            arr[i] = arr[i + 1];

  

        return n - 1;

    }

  

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

    public static void Main()

    {

  

        int i;

        int[] arr = { 10, 20, 30, 40, 50 };

  

        int n = arr.Length;

        int key = 30;

  

        Console.Write("Array before deletion:\n");

        for (i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

  

        n = deleteElement(arr, n, key);

  

        Console.Write("\n\nArray after deletion:\n");

        for (i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Array before deletion
10 20 30 40 50 

Array after deletion
10 20 40 50 

Поиск: O (Log n) [Использование бинарного поиска]
Вставить: O (n) [В худшем случае все элементы могут быть перемещены]
Удалить: O (n) [В худшем случае все элементы могут быть перемещены]

Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes