Minimum swaps so that binary search can be applied | Function to find minimum swaps . ; Here we are getting number of smaller and greater elements of k . ; Here we are calculating the actual position of k in the array . ; Implementing binary search as per the above - discussed cases . ; If we find the k . ; If we need minimum element swap . ; Else the element is at the right position . ; If we need maximum element swap . ; Else element is at the right position ; Calculating the required swaps . ; If it is impossible . ; Driver function
def findMinimumSwaps ( arr , n , k ) : NEW_LINE INDENT num_min = num_max = need_minimum = 0 NEW_LINE need_maximum = swaps = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] < k ) : NEW_LINE INDENT num_min += 1 NEW_LINE DEDENT elif ( arr [ i ] > k ) : NEW_LINE INDENT num_max += 1 NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] == k ) : NEW_LINE INDENT pos = i NEW_LINE break NEW_LINE DEDENT DEDENT left = 0 NEW_LINE right = n - 1 NEW_LINE while ( left <= right ) : NEW_LINE INDENT mid = ( left + right ) // 2 NEW_LINE if ( arr [ mid ] == k ) : NEW_LINE INDENT break NEW_LINE DEDENT elif ( arr [ mid ] > k ) : NEW_LINE INDENT if ( pos > mid ) : NEW_LINE INDENT need_minimum += 1 NEW_LINE DEDENT else : NEW_LINE INDENT num_min -= 1 NEW_LINE DEDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( pos < mid ) : NEW_LINE INDENT need_maximum += 1 NEW_LINE DEDENT else : NEW_LINE INDENT num_max -= 1 NEW_LINE DEDENT right = mid - 1 NEW_LINE DEDENT DEDENT if ( need_minimum > need_maximum ) : NEW_LINE INDENT swaps = swaps + need_maximum NEW_LINE num_min = num_min - need_maximum NEW_LINE need_minimum = ( need_minimum - need_maximum ) NEW_LINE need_maximum = 0 NEW_LINE DEDENT else : NEW_LINE INDENT swaps = swaps + need_minimum NEW_LINE num_max = num_max - need_minimum NEW_LINE need_maximum = ( need_maximum - need_minimum ) NEW_LINE need_minimum = 0 NEW_LINE DEDENT if ( need_maximum > num_max or need_minimum > num_min ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return ( swaps + need_maximum + need_minimum ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 10 , 6 , 7 , 2 , 5 , 4 ] NEW_LINE k = 4 NEW_LINE n = len ( arr ) NEW_LINE print ( findMinimumSwaps ( arr , n , k ) ) NEW_LINE DEDENT