Minimum swaps so that binary search can be applied | Java program to find Minimum number of swaps to get the position of the element if we provide an unsorted array to binary search . ; 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
public class GFG { static int findMinimumSwaps ( int [ ] arr , int n , int k ) { int pos = 0 , num_min , num_max , need_minimum , need_maximum , swaps ; num_min = num_max = need_minimum = 0 ; need_maximum = swaps = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] < k ) { num_min ++ ; } else if ( arr [ i ] > k ) { num_max ++ ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] == k ) { pos = i ; break ; } } int left , right , mid ; left = 0 ; right = n - 1 ; while ( left <= right ) { mid = ( left + right ) / 2 ; if ( arr [ mid ] == k ) { break ; } else if ( arr [ mid ] > k ) { if ( pos > mid ) { need_minimum ++ ; } else { num_min -- ; } left = mid + 1 ; } else { if ( pos < mid ) { need_maximum ++ ; } else { num_max -- ; } right = mid - 1 ; } } if ( need_minimum > need_maximum ) { swaps = swaps + need_maximum ; num_min = num_min - need_maximum ; need_minimum = need_minimum - need_maximum ; need_maximum = 0 ; } else { swaps = swaps + need_minimum ; num_max = num_max - need_minimum ; need_maximum = need_maximum - need_minimum ; need_minimum = 0 ; } if ( need_maximum > num_max need_minimum > num_min ) { return - 1 ; } else { return ( swaps + need_maximum + need_minimum ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 10 , 6 , 7 , 2 , 5 , 4 } , k = 4 ; int n = arr . length ; System . out . println ( findMinimumSwaps ( arr , n , k ) ) ; } }