Kth smallest element in the array using constant space when array can 't be modified | Function to return the kth smallest element from the array ; Minimum and maximum element from the array ; Modified binary search ; To store the count of elements from the array which are less than mid and the elements which are equal to mid ; If mid is the kth smallest ; If the required element is less than mid ; If the required element is greater than mid ; Driver code
def kthSmallest ( arr , k , n ) : NEW_LINE INDENT low = min ( arr ) ; NEW_LINE high = max ( arr ) ; NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 ; NEW_LINE countless = 0 ; countequal = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] < mid ) : NEW_LINE INDENT countless += 1 ; NEW_LINE DEDENT elif ( arr [ i ] == mid ) : NEW_LINE INDENT countequal += 1 ; NEW_LINE DEDENT DEDENT if ( countless < k and ( countless + countequal ) >= k ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT elif ( countless >= k ) : NEW_LINE INDENT high = mid - 1 ; NEW_LINE DEDENT elif ( countless < k and countless + countequal < k ) : NEW_LINE INDENT low = mid + 1 ; NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 7 , 10 , 4 , 3 , 20 , 15 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE k = 3 ; NEW_LINE print ( kthSmallest ( arr , k , n ) ) ; NEW_LINE DEDENT