Median of difference of all pairs from an Array | Function check if mid can be median index of the difference array ; Size of the array ; Total possible no of pair possible ; The index of the element in the difference of all pairs from the array ; Count the number of pairs having difference <= mid ; If the difference between end and first element is less then or equal to mid ; Checking for the no of element less than or equal to mid is greater than median or not ; Function to calculate the median of differences of all pairs from the array ; Size of the array ; Initialising the low and high ; Binary search ; Calculate mid ; If mid can be the median of the array ; Returning the median of the differences of pairs from the array ; Driver Code
function possible ( mid , a ) { let n = a . length ; let total = parseInt ( ( n * ( n - 1 ) ) / 2 ) ; let need = parseInt ( ( total + 1 ) / 2 ) ; let count = 0 ; let start = 0 , end = 1 ; while ( end < n ) { if ( a [ end ] - a [ start ] <= mid ) { end ++ ; } else { count += ( end - start - 1 ) ; start ++ ; } } if ( end == n && start < end && a [ end - 1 ] - a [ start ] <= mid ) { let t = end - start - 1 ; count += parseInt ( t * ( t + 1 ) / 2 ) ; } if ( count >= need ) return true ; else return false ; } function findMedian ( a ) { let n = a . length ; let low = 0 , high = a [ n - 1 ] - a [ 0 ] ; while ( low <= high ) { let mid = ( low + high ) / 2 ; if ( possible ( mid , a ) ) high = mid - 1 ; else low = mid + 1 ; } return high + 1 ; } let a = [ 1 , 7 , 5 , 2 ] ; a . sort ( ) ; document . write ( findMedian ( a ) ) ;