Convert an Array to reduced for using Binary Search
Given an array arr[] consisting of N distinct integers, the task is to convert the given array into a sequence of first N non-negative integers, i.e. [0, N – 1] such that the order of the elements is the same, i.e. 0 is placed at the index of the smallest array element, 1 at the index of the second smallest element, and so on.
Examples:
Input: arr[] = {10, 40, 20}
Output: 0 2 1Input: arr[] = {5, 10, 40, 30, 20}
Output: 0 1 4 3 2
Hashing-Based Approach: Please refer to the Set 1 post of this article for the hashing-based approach.
Time Complexity: O(N* log N)
Auxiliary Space: O(N)
Vector Of Pairs Based Approach: Please refer to the Set 2 post of this article for the approach using the vector of pairs.
Time Complexity: O(N* log N)
Auxiliary Space: O(N)
Binary Search-based Approach: Follow the steps to solve the problem:
- Initialize an array, say brr[] and store all the elements of the array arr[] into brr[].
- Sort the array brr[] in ascending order.
- Traverse the given array arr[] and for each element i.e., arr[i] find the lower_bound of arr[i] in the array brr[] and print the index of is as the result for the current element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the reduced form // of the given array arr[] void convert( int arr[], int n) { // Stores the sorted form of the // the given array arr[] int brr[n]; for ( int i = 0; i < n; i++) brr[i] = arr[i]; // Sort the array brr[] sort(brr, brr + n); // Traverse the given array arr[] for ( int i = 0; i < n; i++) { int l = 0, r = n - 1, mid; // Perform the Binary Search while (l <= r) { // Calculate the value of // mid mid = (l + r) / 2; if (brr[mid] == arr[i]) { // Print the current // index and break cout << mid << ' ' ; break ; } // Update the value of l else if (brr[mid] < arr[i]) { l = mid + 1; } // Update the value of r else { r = mid - 1; } } } } // Driver Code int main() { int arr[] = { 10, 20, 15, 12, 11, 50 }; int N = sizeof (arr) / sizeof (arr[0]); convert(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to find the reduced form // of the given array arr[] static void convert( int arr[], int n) { // Stores the sorted form of the // the given array arr[] int brr[] = new int [n]; for ( int i = 0 ; i < n; i++) brr[i] = arr[i]; // Sort the array brr[] Arrays.sort(brr); // Traverse the given array arr[] for ( int i = 0 ; i < n; i++) { int l = 0 , r = n - 1 , mid; // Perform the Binary Search while (l <= r) { // Calculate the value of // mid mid = (l + r) / 2 ; if (brr[mid] == arr[i]) { // Print the current // index and break System.out.print(mid + " " ); break ; } // Update the value of l else if (brr[mid] < arr[i]) { l = mid + 1 ; } // Update the value of r else { r = mid - 1 ; } } } } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 20 , 15 , 12 , 11 , 50 }; int N = arr.length; convert(arr, N); } } // This code is contributed by Kingash. |
Python3
# Python3 program for the above approach # Function to find the reduced form # of the given array arr[] def convert(arr, n): # Stores the sorted form of the # the given array arr[] brr = [i for i in arr] # Sort the array brr[] brr = sorted (brr) # Traverse the given array arr[] for i in range (n): l, r, mid = 0 , n - 1 , 0 # Perform the Binary Search while (l < = r): # Calculate the value of # mid mid = (l + r) / / 2 if (brr[mid] = = arr[i]): # Print the current # index and break print (mid,end = " " ) break # Update the value of l elif (brr[mid] < arr[i]): l = mid + 1 # Update the value of r else : r = mid - 1 # Driver Code if __name__ = = '__main__' : arr = [ 10 , 20 , 15 , 12 , 11 , 50 ] N = len (arr) convert(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the reduced form // of the given array arr[] static void convert( int [] arr, int n) { // Stores the sorted form of the // the given array arr[] int [] brr = new int [n]; for ( int i = 0; i < n; i++) brr[i] = arr[i]; // Sort the array brr[] Array.Sort(brr); // Traverse the given array arr[] for ( int i = 0; i < n; i++) { int l = 0, r = n - 1, mid; // Perform the Binary Search while (l <= r) { // Calculate the value of // mid mid = (l + r) / 2; if (brr[mid] == arr[i]) { // Print the current // index and break Console.Write(mid + " " ); break ; } // Update the value of l else if (brr[mid] < arr[i]) { l = mid + 1; } // Update the value of r else { r = mid - 1; } } } } // Driver Code public static void Main( string [] args) { int [] arr = { 10, 20, 15, 12, 11, 50 }; int N = arr.Length; convert(arr, N); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach // Function to find the reduced form // of the given array arr[] function convert(arr, n) { // Stores the sorted form of the // the given array arr[] var brr = Array(n).fill(0); var i; for (i = 0; i < n; i++) brr[i] = arr[i]; // Sort the array brr[] brr.sort(); // Traverse the given array arr[] for (i = 0; i < n; i++) { var l = 0, r = n - 1, mid; // Perform the Binary Search while (l <= r) { // Calculate the value of // mid mid = parseInt((l + r) / 2,10); if (brr[mid] == arr[i]) { // Print the current // index and break document.write(mid + ' ' ); break ; } // Update the value of l else if (brr[mid] < arr[i]) { l = mid + 1; } // Update the value of r else { r = mid - 1; } } } } // Driver Code var arr = [10, 20, 15, 12, 11, 50]; var N = arr.length; convert(arr, N); // This code is contributed by SURENDRA_GANGWAR. </script> |
0 4 3 2 1 5
Time Complexity: O(N * log N)
Auxiliary Space: O(N)