Переупорядочить массив, чтобы найти K с использованием алгоритма двоичного поиска без сортировки

Опубликовано: 22 Сентября, 2022

Учитывая массив, arr[] из N различных целых чисел и целое число K , задача состоит в том, чтобы переупорядочить данный массив таким образом, чтобы K можно было найти с помощью алгоритма бинарного поиска в переупорядоченном массиве. Обратите внимание, массив не подлежит сортировке.

Примеры:

Input: arr[] = {10, 7, 2, 5, 3, 8}, K = 7
Output: 3 7 8 5 2 10  
Explanation: Finding K in output array {3, 7, 8, 5, 2, 10} using Binary Search 
— initially, left (L) = 0, right (R) = 5, mid = 2, i.e. 8 (not equal to K) 
— since 8 > K, therefore left (L) = 0, right (R) = 1, mid = 0, i.e.  3(not equal to K) 
— since 3 < K, therefore left (L) = 1, right (R) = 1, mid = 1, i.e. 7 (which is equal to K) 
Hence K can be found in output array using Binary Search, even the array is unsorted. 
 

Input: arr[] = {10, 7, 2, 5, 8, 6}, K = 6
Output: 8 7 5 10 2 6 

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  1. An integer K can be found in a sorted array arr[] using the binary search algorithm as follows:
    1. Initially, L = 0 and R = N-1.
    2. While L is less than or equal to R:
      1. Find the mid point of the current range [L, R] as mid = (L+R)/2.
      2. If arr[mid] is equal to K, it returns true.
      3. Else, if arr[mid] is greater than K, then update R to mid-1 i.e, all elements right of mid are skipped.
      4. Else, if arr[mid] is less than K, then update L to mid+1 i.e, all elements left of mid are skipped.
    3. If K is not found, then return false.
  2. The binary search algorithm may fail on unsorted arrays because the array doesn’t meet the criteria of the array being monotonically increasing or decreasing. But, sometimes the binary search algorithm may also work on unsorted arrays.
  3. For example, suppose the given array, arr[] is equal to {2, 1, 5, 4, 3} and K is equal to 2. Then the algorithm works as:
    1. In the first iteration:
      • The L=0 and R= 4, therefore mid = (4+0)/2 =2. 
      • The arr[2] (=5) is greater than 2,  so assign mid-1 to R. Now R becomes 1.
    2. In the second Iteration:
      • The L=0 and R= 1, therefore mid = (1+0)/2 =0.
      • The arr[0] (=2) is equal to 2. Therefore, return true.
  4. Therefore, from above, it can be observed that, to go the index X, from a position mid, there are two cases:
    1. If mid is less than X, then arr[mid] has to be less than arr[X], to move towards index X, which lies on the right side of mid.
    2. Else, if mid is greater than X then arr[mid] has to be greater than arr[X], to move towards index X, which lies on the left side of mid

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив, скажем, ans[] со всеми элементами массива как -1 , чтобы сохранить переупорядоченный массив.
  • Кроме того, инициализируйте два вектора, скажем, меньше и больше , чтобы хранить элементы меньше и больше, чем K .
  • Пройдите массив, arr[] и поместите текущий элемент в меньший , если он меньше K . В противном случае вставьте его в больше , если оно больше, чем K .
  • Найдите индекс элемента K в массиве arr[] и затем присвойте его значение K .
  • Инициализируйте две переменные, скажем, low как 0 и high как N-1 , чтобы выполнить бинарный поиск.
  • Повторяйте до тех пор, пока низкий уровень не станет меньше или равен высокому , и выполните следующие шаги:
    • Найдите середину текущего диапазона [low, high] и сохраните ее в переменной, скажем, mid .
    • Если mid меньше K , то сделайте следующее:
      • Если small.size() равно 0 , то выведите « -1 » и вернитесь.
      • В противном случае присвойте последнему элементу вектора, меньшему , значение ans[mid] , а затем извлеките последний элемент из меньшего .
    • Если mid больше, чем K , то сделайте следующее:
      • Если больше.size() равно 0 , то выведите « -1 » и вернитесь.
      • В противном случае присвойте последнему элементу вектора, больше , значение ans[mid] , а затем извлеките последний элемент большего значения.
    • Если mid равно K , тогда присвойте arr[K] ans[mid] и затем разбейте.
  • После выполнения вышеуказанных шагов пройдитесь по массиву, ans[] и, если текущий элемент равен « -1 », т.е. не заполнен, то присвойте ему любой неиспользуемый элемент.
  • Наконец, напечатайте массив ans[] как переупорядоченный массив.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ