Rearrange Array to find K using Binary Search algorithm without sorting | Java 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
import java . util . * ; public class GFG { static void Rearrange ( int arr [ ] , int K , int N ) { int ans [ ] = new int [ N + 1 ] ; int f = - 1 ; for ( int i = 0 ; i < N ; i ++ ) { ans [ i ] = - 1 ; } for ( int i = 0 ; i < arr . length ; i ++ ) { if ( arr [ i ] == K ) { K = i ; break ; } } Vector < Integer > smaller = new Vector < Integer > ( ) ; Vector < Integer > greater = new Vector < Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] < arr [ K ] ) smaller . add ( arr [ i ] ) ; else if ( arr [ i ] > arr [ K ] ) greater . add ( 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 . lastElement ( ) ; smaller . remove ( smaller . size ( ) - 1 ) ; low = mid + 1 ; } else { if ( greater . size ( ) == 0 ) { break ; } ans [ mid ] = greater . lastElement ( ) ; greater . remove ( greater . size ( ) - 1 ) ; high = mid - 1 ; } } if ( f == - 1 ) { System . out . println ( - 1 ) ; return ; } for ( int i = 0 ; i < N ; i ++ ) { 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 ) ; } } } for ( int i = 0 ; i < N ; i ++ ) System . out . print ( ans [ i ] + " ▁ " ) ; System . out . println ( ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 10 , 7 , 2 , 5 , 3 , 8 } ; int K = 7 ; int N = arr . length ; Rearrange ( arr , K , N ) ; } }