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
def possible ( mid , a ) : NEW_LINE INDENT n = len ( a ) ; NEW_LINE total = ( n * ( n - 1 ) ) // 2 ; NEW_LINE need = ( total + 1 ) // 2 ; NEW_LINE count = 0 ; NEW_LINE start = 0 ; end = 1 ; NEW_LINE while ( end < n ) : NEW_LINE INDENT if ( a [ end ] - a [ start ] <= mid ) : NEW_LINE INDENT end += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT count += ( end - start - 1 ) ; NEW_LINE start += 1 ; NEW_LINE DEDENT DEDENT if ( end == n and start < end and a [ end - 1 ] - a [ start ] <= mid ) : NEW_LINE INDENT t = end - start - 1 ; NEW_LINE count += ( t * ( t + 1 ) // 2 ) ; NEW_LINE DEDENT if ( count >= need ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT else : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT def findMedian ( a ) : NEW_LINE INDENT n = len ( a ) ; NEW_LINE low = 0 ; high = a [ n - 1 ] - a [ 0 ] ; NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) // 2 ; NEW_LINE if ( possible ( mid , a ) ) : NEW_LINE INDENT high = mid - 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 ; NEW_LINE DEDENT DEDENT return high + 1 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 7 , 5 , 2 ] ; NEW_LINE a . sort ( ) NEW_LINE print ( findMedian ( a ) ) ; NEW_LINE DEDENT