Given an array, arr[] of N distinct integers and an integer K, the task is to rearrange the given array in such a way, that K can be found with the help of Binary Search Algorithm in the rearranged array. Please note, the array is not to be sorted.
Examples:
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
Approach: The given problem can be solved based on the following observations:
- An integer K can be found in a sorted array arr[] using the binary search algorithm as follows:
- Initially, L = 0 and R = N-1.
- While L is less than or equal to R:
- Find the mid point of the current range [L, R] as mid = (L+R)/2.
- If arr[mid] is equal to K, it returns true.
- Else, if arr[mid] is greater than K, then update R to mid-1 i.e, all elements right of mid are skipped.
- Else, if arr[mid] is less than K, then update L to mid+1 i.e, all elements left of mid are skipped.
- If K is not found, then return false.
- 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.
- 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:
- 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.
- 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.
- Therefore, from above, it can be observed that, to go the index X, from a position mid, there are two cases:
- 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.
- 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
Follow the steps below to solve the problem:
- Initialize an array, say ans[] with all array elements as -1 to store the rearranged array.
- Also, initialize two vectors say smaller and greater to store the elements smaller and greater than K.
- Traverse the array, arr[] and push the current element into smaller if it is less than K. Otherwise, push it into greater if it is greater than K.
- Find the index of the element K in the array arr[] and then assign the value of it to K.
- Initialize two variables, say low as 0 and high as N-1, to perform a binary search.
- Iterate until low is less than or equal to high and perform the following steps:
- Find the mid of the current range [low, high] and store it in a variable, say mid.
- If mid is less than K, then do the following:
- If smaller.size() is 0, then print “-1” and return.
- Otherwise, assign the last element of the vector, smaller to ans[mid], and then pop the last element of smaller.
- If mid is greater than K, then do the following:
- If greater.size() is 0, then print “-1” and return.
- Otherwise, assign the last element of the vector, greater to ans[mid], and then pop the last element of greater.
- If mid is equal to K, then assign arr[K] to ans[mid] and then break.
- After completing the above steps, traverse the array, ans[] and if the current element is “-1” i.e not filled, then assign any unused element to it.
- Finally, print the array ans[] as the rearranged array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the arrayvoid Rearrange(int arr[], int K, int N){ // Stores the rearranged array int ans[N + 1]; // Stores whether the arrangement // is possible or not int f = -1; for (int i = 0; i < N; i++) { ans[i] = -1; } // Update K with the position of K K = find(arr, arr + N, K) - arr; // Stores all elements lesser than // and greater than in vector smaller // and greater respectively vector<int> smaller, greater; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is less than arr[K] if (arr[i] < arr[K]) smaller.push_back(arr[i]); // Else else if (arr[i] > arr[K]) greater.push_back(arr[i]); } int low = 0, high = N - 1; // Iterate until low is less than or // equal to high while (low <= high) { // Stores mid point int mid = (low + high) / 2; // If mid is equal to K if (mid == K) { ans[mid] = arr[K]; f = 1; break; } // If mid is less than K else if (mid < K) { if (smaller.size() == 0) { break; } ans[mid] = smaller.back(); smaller.pop_back(); low = mid + 1; } // If mid is greater than K else { if (greater.size() == 0) { break; } ans[mid] = greater.back(); greater.pop_back(); high = mid - 1; } } // If f is -1 if (f == -1) { cout << -1 << endl; return; } // Iterate in the range [1, N] for (int i = 0; i < N; i++) { // If ans[i] is equal to -1 if (ans[i] == -1) { if (smaller.size()) { ans[i] = smaller.back(); smaller.pop_back(); } else if (greater.size()) { ans[i] = greater.back(); greater.pop_back(); } } } // Print the rearranged array for (int i = 0; i < N; i++) cout << ans[i] << " "; cout << endl;}// Driver Codeint main(){ // Input int arr[] = { 10, 7, 2, 5, 3, 8 }; int K = 7; int N = sizeof(arr) / sizeof(arr[0]); // Function Call Rearrange(arr, K, N); return 0;} |
Java
// Java program for the above approach import java.util.*;public class GFG{ // Function to rearrange the arraystatic void Rearrange(int arr[], int K, int N){ // Stores the rearranged array int ans[] = new int[N + 1]; // Stores whether the arrangement // is possible or not int f = -1; for (int i = 0; i < N; i++) { ans[i] = -1; } // Update K with the position of K for (int i = 0; i < arr.length; i++) { if (arr[i] == K) { K = i; break; } } // Stores all elements lesser than // and greater than in vector smaller // and greater respectively Vector<Integer> smaller = new Vector<Integer>(); Vector<Integer> greater = new Vector<Integer>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is less than arr[K] if (arr[i] < arr[K]) smaller.add(arr[i]); // Else else if (arr[i] > arr[K]) greater.add(arr[i]); } int low = 0, high = N - 1; // Iterate until low is less than or // equal to high while (low <= high) { // Stores mid point int mid = (low + high) / 2; // If mid is equal to K if (mid == K) { ans[mid] = arr[K]; f = 1; break; } // If mid is less than K else if (mid < K) { if (smaller.size() == 0) { break; } ans[mid] = smaller.lastElement(); smaller.remove(smaller.size()-1); low = mid + 1; } // If mid is greater than K else { if (greater.size() == 0) { break; } ans[mid] = greater.lastElement(); greater.remove(greater.size()-1); high = mid - 1; } } // If f is -1 if (f == -1) { System.out.println(-1 ); return; } // Iterate in the range [1, N] for (int i = 0; i < N; i++) { // If ans[i] is equal to -1 if (ans[i] == -1) { if (smaller.size()>0) { ans[i] = smaller.lastElement(); smaller.remove(smaller.size()-1); } else if (greater.size()>0) { ans[i] = greater.lastElement(); greater.remove(greater.size()-1); } } } // Print the rearranged array for (int i = 0; i < N; i++) System.out.print(ans[i] +" "); System.out.println();} // Driver code public static void main(String args[]) { // Input int arr[] = { 10, 7, 2, 5, 3, 8 }; int K = 7; int N = arr.length; // Function Call Rearrange(arr, K, N); }}// This code is contributed by SoumikMondal |
Python3
# Python 3 program for the above approach# Function to rearrange the arraydef Rearrange(arr, K, N): # Stores the rearranged array ans = [0]*(N + 1) # Stores whether the arrangement # is possible or not f = -1 for i in range(N): ans[i] = -1 # Update K with the position of K K = arr.index(K) # Stores all elements lesser than # and greater than in vector smaller # and greater respectively smaller = [] greater = [] # Traverse the array arr[] for i in range(N): # If arr[i] is less than arr[K] if (arr[i] < arr[K]): smaller.append(arr[i]) # Else elif (arr[i] > arr[K]): greater.append(arr[i]) low = 0 high = N - 1 # Iterate until low is less than or # equal to high while (low <= high): # Stores mid point mid = (low + high) // 2 # If mid is equal to K if (mid == K): ans[mid] = arr[K] f = 1 break # If mid is less than K elif (mid < K): if (len(smaller) == 0): break ans[mid] = smaller[-1] smaller.pop() low = mid + 1 # If mid is greater than K else: if (len(greater) == 0): break ans[mid] = greater[-1] greater.pop() high = mid - 1 # If f is -1 if (f == -1): print(-1) return # Iterate in the range [1, N] for i in range(N): # If ans[i] is equal to -1 if (ans[i] == -1): if (len(smaller)): ans[i] = smaller[-1] smaller.pop() elif (len(greater)): ans[i] = greater[-1] greater.pop() # Print the rearranged array for i in range(N): print(ans[i], end=" ") print()# Driver Codeif __name__ == "__main__": # Input arr = [10, 7, 2, 5, 3, 8] K = 7 N = len(arr) # Function Call Rearrange(arr, K, N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to rearrange the array static void Rearrange(int []arr, int K, int N) { // Stores the rearranged array int []ans = new int[N + 1]; // Stores whether the arrangement // is possible or not int f = -1; for (int i = 0; i < N; i++) { ans[i] = -1; } // Update K with the position of K for (int i = 0; i < arr.Length; i++) { if (arr[i] == K) { K = i; break; } } // Stores all elements lesser than // and greater than in vector smaller // and greater respectively List<int> smaller = new List<int>(); List<int> greater = new List<int>(); // Traverse the array []arr for (int i = 0; i < N; i++) { // If arr[i] is less than arr[K] if (arr[i] < arr[K]) smaller.Add(arr[i]); // Else else if (arr[i] > arr[K]) greater.Add(arr[i]); } int low = 0, high = N - 1; // Iterate until low is less than or // equal to high while (low <= high) { // Stores mid point int mid = (low + high) / 2; // If mid is equal to K if (mid == K) { ans[mid] = arr[K]; f = 1; break; } // If mid is less than K else if (mid < K) { if (smaller.Count == 0) { break; } ans[mid] = smaller[smaller.Count-1]; smaller.RemoveAt(smaller.Count-1); low = mid + 1; } // If mid is greater than K else { if (greater.Count == 0) { break; } ans[mid] = greater[greater.Count-1]; greater.RemoveAt(greater.Count-1); high = mid - 1; } } // If f is -1 if (f == -1) { Console.WriteLine(-1 ); return; } // Iterate in the range [1, N] for (int i = 0; i < N; i++) { // If ans[i] is equal to -1 if (ans[i] == -1) { if (smaller.Count>0) { ans[i] = smaller[smaller.Count-1]; smaller.RemoveAt(smaller.Count-1); } else if (greater.Count>0) { ans[i] = greater[greater.Count-1]; greater.RemoveAt(greater.Count-1); } } } // Print the rearranged array for (int i = 0; i < N; i++) Console.Write(ans[i] +" "); Console.WriteLine(); } // Driver code public static void Main(String []args) { // Input int []arr = { 10, 7, 2, 5, 3, 8 }; int K = 7; int N = arr.Length; // Function Call Rearrange(arr, K, N); }}// This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program for the above approach // Function to rearrange the array function Rearrange(arr, K, N) { // Stores the rearranged array let ans = new Array(N + 1); // Stores whether the arrangement // is possible or not let f = -1; for (let i = 0; i < N; i++) { ans[i] = -1; } // Update K with the position of K for (let i = 0; i < arr.length; i++) { if (arr[i] == K) { K = i; break; } } // Stores all elements lesser than // and greater than in vector smaller // and greater respectively let smaller = []; let greater = []; // Traverse the array arr[] for (let i = 0; i < N; i++) { // If arr[i] is less than arr[K] if (arr[i] < arr[K]) smaller.push(arr[i]); // Else else if (arr[i] > arr[K]) greater.push(arr[i]); } let low = 0, high = N - 1; // Iterate until low is less than or // equal to high while (low <= high) { // Stores mid point let mid = Math.floor((low + high) / 2); // If mid is equal to K if (mid == K) { ans[mid] = arr[K]; f = 1; break; } // If mid is less than K else if (mid < K) { if (smaller.length == 0) { break; } ans[mid] = smaller[smaller.length - 1]; smaller.pop(); low = mid + 1; } // If mid is greater than K else { if (greater.length == 0) { break; } ans[mid] = greater[greater.length - 1]; greater.pop(); high = mid - 1; } } // If f is -1 if (f == -1) { document.write(-1); return; } // Iterate in the range [1, N] for (let i = 0; i < N; i++) { // If ans[i] is equal to -1 if (ans[i] == -1) { if (smaller.length != 0) { ans[i] = smaller[smaller.length - 1]; smaller.pop(); } else if (greater.length != 0) { ans[i] = greater[greater.length - 1]; greater.pop; } } } // Print the rearranged array for (let i = 0; i < N; i++) document.write(ans[i] + " "); document.write("<br>") } // Driver Code // Input let arr = [10, 7, 2, 5, 3, 8]; let K = 7; let N = arr.length; // Function Call Rearrange(arr, K, N);// This code is contributed by Potta Lokesh </script> |
Output
3 7 8 5 2 10
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
