Рубрики

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

Задан массив, который отсортирован, но после сортировки некоторые элементы перемещаются в одну из соседних позиций, т. Е. Arr [i] может присутствовать в arr [i + 1] или arr [i-1]. Напишите эффективную функцию для поиска элемента в этом массиве , В основном элемент arr [i] может быть заменен только на arr [i + 1] или на arr [i-1].

Например, рассмотрим массив {2, 3, 10, 4, 40}, 4 перемещен в следующую позицию и 10 перемещен в предыдущую позицию.

Пример :

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2 
Output is index of 40 in given array

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 90
Output: -1
-1 is returned to indicate element is not present

Простое решение заключается в линейном поиске заданного ключа в заданном массиве. Временная сложность этого решения составляет O (n). Мы можем изменить бинарный поиск, чтобы сделать это за время O (Logn).

Идея состоит в том, чтобы сравнить ключ со средними 3 элементами, если они есть, и вернуть индекс. Если нет, то сравните ключ со средним элементом, чтобы решить, идти ли в левую или правую половину. Сравнения со средним элементом достаточно, так как все элементы после середины + 2 должны быть больше, чем середина элемента, а все элементы до середины 2 должны быть меньше, чем средний элемент.

Ниже приводится реализация этого подхода.

C ++

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

  
// Функция рекурсивного бинарного поиска.
// Возвращает индекс х в данном массиве
// присутствует arr [l..r], иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

if (r >= l)

{

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует в

        // одна из трех средних позиций

        if (arr[mid] == x) 

            return mid;

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

            return (mid - 1);

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

            return (mid + 1);

  

        // Если элемент меньше среднего, то

        // он может присутствовать только в левом подмассиве

        if (arr[mid] > x) 

            return binarySearch(arr, l, mid - 2, x);

  

        // иначе элемент может присутствовать только

        // в правом подмассиве

        return binarySearch(arr, mid + 2, r, x);

}

  
// Мы достигаем здесь, когда элемент отсутствует в массиве

return -1;

}

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

int main(void)

{

int arr[] = {3, 2, 10, 4, 40};

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

int x = 4;

int result = binarySearch(arr, 0, n - 1, x);

(result == -1) ? printf("Element is not present in array")

               : printf("Element is present at index %d"

                         result);

return 0;

}

Джава

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

class GFG

{

    // Функция рекурсивного бинарного поиска.

    // Возвращает индекс х в данном массиве

    // присутствует arr [l..r], иначе -1

    int binarySearch(int arr[], int l, int r, int x)

    {

        if (r >= l)

        {

            int mid = l + (r - l) / 2;

  

            // Если элемент присутствует в

            // одна из трех средних позиций

            if (arr[mid] == x) 

                return mid;

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

                return (mid - 1);

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

                return (mid + 1);

  

            // Если элемент меньше среднего, то

            // он может присутствовать только в левом подмассиве

            if (arr[mid] > x) 

                return binarySearch(arr, l, mid - 2, x);

  

            // иначе элемент может присутствовать только

            // в правом подмассиве

            return binarySearch(arr, mid + 2, r, x);

        }

  

        // Мы достигаем здесь, когда элемент

        // отсутствует в массиве

        return -1;

    }

  

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

    public static void main(String args[])

    {

        GFG ob = new GFG();

        int arr[] = {3, 2, 10, 4, 40};

        int n = arr.length;

        int x = 4;

        int result = ob.binarySearch(arr, 0, n - 1, x);

        if(result == -1)

            System.out.println("Element is not present in array");

        else

            System.out.println("Element is present at index " +

                                result);

    }

}

  
// Этот код предоставлен Раджатом Мишрой

python3

# Python 3 программа для поиска элемента
# в почти отсортированном массиве

  
# Функция рекурсивного бинарного поиска.
# Возвращает индекс x в данном массиве arr [l..r]
# присутствует, иначе -1

def binarySearch(arr, l, r, x):

  

    if (r >= l):

          

        mid = int(l + (r - l) / 2)

          

        # Если элемент присутствует в одном

        № средней 3 позиции

        if (arr[mid] == x): return mid

        if (mid > l and arr[mid - 1] == x): 

            return (mid - 1)

        if (mid < r and arr[mid + 1] == x):

            return (mid + 1)

              

        # Если элемент меньше середины, то

        # может присутствовать только в левом подмассиве

        if (arr[mid] > x):

            return binarySearch(arr, l, mid - 2, x)

          

        # Иначе элемент может только

        # присутствовать в правом подмассиве

        return binarySearch(arr, mid + 2, r, x)

  

    # Мы достигаем здесь, когда элемент

    # нет в массиве

    return -1

  
Код водителя

arr = [3, 2, 10, 4, 40]

n = len(arr)

x = 4

result = binarySearch(arr, 0, n - 1, x)

if (result == -1): 

    print("Element is not present in array"

else:

    print("Element is present at index", result)

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

C #

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

using System;

  

class GFG

{

    // Функция рекурсивного бинарного поиска.

    // Возвращает индекс х в данном массиве

    // присутствует arr [l..r], иначе -1

    int binarySearch(int []arr, int l, int r, int x)

    {

        if (r >= l)

        {

            int mid = l + (r - l) / 2;

  

            // Если элемент присутствует в

            // одна из трех средних позиций

            if (arr[mid] == x) 

                return mid;

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

                return (mid - 1);

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

                return (mid + 1);

  

            // Если элемент меньше среднего, то

            // он может присутствовать только в левом подмассиве

            if (arr[mid] > x) 

                return binarySearch(arr, l, mid - 2, x);

  

            // иначе элемент может присутствовать только

            // в правом подмассиве

            return binarySearch(arr, mid + 2, r, x);

        }

  

        // Мы достигаем здесь, когда элемент

        // отсутствует в массиве

        return -1;

    }

  

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

    public static void Main()

    {

        GFG ob = new GFG();

        int []arr = {3, 2, 10, 4, 40};

        int n = arr.Length;

        int x = 4;

        int result = ob.binarySearch(arr, 0, n - 1, x);

        if(result == -1)

            Console.Write("Element is not present in array");

        else

            Console.Write("Element is present at index " +

                           result);

    }

}

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

PHP

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

  
// Функция рекурсивного бинарного поиска.
// Возвращает индекс х в данном массиве
// присутствует arr [l..r], иначе -1

function binarySearch($arr, $l, $r, $x)

{

    if ($r >= $l)

    {

        $mid = $l + ($r - $l) / 2;

  

        // Если элемент присутствует в

        // одна из трех средних позиций

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

            return $mid;

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

            return ($mid - 1);

        if ($mid < $r && $arr[$mid + 1] == $x

            return ($mid + 1);

  

        // Если элемент меньше среднего, то

        // он может присутствовать только в левом подмассиве

        if ($arr[$mid] > $x

            return binarySearch($arr, $l

                           $mid - 2, $x);

  

        // иначе элемент может присутствовать только

        // в правом подмассиве

        return binarySearch($arr, $mid + 2, 

                                    $r, $x);

}

  
// Мы достигаем здесь, когда элемент
// нет в массиве

return -1;

}

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

$arr = array(3, 2, 10, 4, 40);

$n = sizeof($arr);

$x = 4;

$result = binarySearch($arr, 0, $n - 1, $x);

if($result == -1) 

    echo("Element is not present in array");

else

    echo("Element is present at index $result");

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


Выход :

Element is present at index 3

Временная сложность вышеуказанной функции составляет O (Logn).

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

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

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

0.00 (0%) 0 votes