Rearrange Array to find K using Binary Search algorithm without sorting | 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
def Rearrange ( arr , K , N ) : NEW_LINE INDENT ans = [ 0 ] * ( N + 1 ) NEW_LINE f = - 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT ans [ i ] = - 1 NEW_LINE DEDENT K = arr . index ( K ) NEW_LINE smaller = [ ] NEW_LINE greater = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] < arr [ K ] ) : NEW_LINE INDENT smaller . append ( arr [ i ] ) NEW_LINE DEDENT elif ( arr [ i ] > arr [ K ] ) : NEW_LINE INDENT greater . append ( arr [ i ] ) NEW_LINE DEDENT DEDENT low = 0 NEW_LINE high = N - 1 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( mid == K ) : NEW_LINE INDENT ans [ mid ] = arr [ K ] NEW_LINE f = 1 NEW_LINE break NEW_LINE DEDENT elif ( mid < K ) : NEW_LINE INDENT if ( len ( smaller ) == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT ans [ mid ] = smaller [ - 1 ] NEW_LINE smaller . pop ( ) NEW_LINE low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( len ( greater ) == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT ans [ mid ] = greater [ - 1 ] NEW_LINE greater . pop ( ) NEW_LINE high = mid - 1 NEW_LINE DEDENT DEDENT if ( f == - 1 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT if ( ans [ i ] == - 1 ) : NEW_LINE INDENT if ( len ( smaller ) ) : NEW_LINE INDENT ans [ i ] = smaller [ - 1 ] NEW_LINE smaller . pop ( ) NEW_LINE DEDENT elif ( len ( greater ) ) : NEW_LINE INDENT ans [ i ] = greater [ - 1 ] NEW_LINE greater . pop ( ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 10 , 7 , 2 , 5 , 3 , 8 ] NEW_LINE K = 7 NEW_LINE N = len ( arr ) NEW_LINE Rearrange ( arr , K , N ) NEW_LINE DEDENT