text: Rearrange Array to find K using Binary Search algorithm without sorting | C ++ program for the above approach ; Function to rearrange the array ; Stores the rearranged array ; Stores whether the arrangement is possible or not ; Update K with the position of K ; Stores all elements lesser than and greater than in vector smaller and greater respectively ; Traverse the array arr [ ] ; If arr [ i ] is less than arr [ K ] ; Else ; Iterate unil low is less than or equal to high ; Stores mid point ; If mid is equal to K ; If mid is less than K ; If mid is greater than K ; If f is - 1 ; Iterate in the range [ 1 , N ] ; If ans [ i ] is equal to - 1 ; Print the rearranged array ; Driver Code ; Input ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void Rearrange ( int arr [ ] , int K , int N ) { int ans [ N + 1 ] ; int f = -1 ; for ( int i = 0 ; i < N ; i ++ ) { ans [ i ] = -1 ; } K = find ( arr , arr + N , K ) - arr ; vector < int > smaller , greater ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] < arr [ K ] ) smaller . push_back ( arr [ i ] ) ; else if ( arr [ i ] > arr [ K ] ) greater . push_back ( arr [ i ] ) ; } int low = 0 , high = N - 1 ; while ( low <= high ) { int mid = ( low + high ) / 2 ; if ( mid == K ) { ans [ mid ] = arr [ K ] ; f = 1 ; break ; } else if ( mid < K ) { if ( smaller . size ( ) == 0 ) { break ; } ans [ mid ] = smaller . back ( ) ; smaller . pop_back ( ) ; low = mid + 1 ; } else { if ( greater . size ( ) == 0 ) { break ; } ans [ mid ] = greater . back ( ) ; greater . pop_back ( ) ; high = mid - 1 ; } } if ( f == -1 ) { cout << -1 << endl ; return ; } for ( int i = 0 ; i < N ; i ++ ) { 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 ( ) ; } } } for ( int i = 0 ; i < N ; i ++ ) cout << ans [ i ] << " ▁ " ; cout << endl ; } int main ( ) { int arr [ ] = { 10 , 7 , 2 , 5 , 3 , 8 } ; int K = 7 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; Rearrange ( arr , K , N ) ; return 0 ; }