Kth Smallest Element in a sorted array formed by reversing subarrays from a random index | ''Function to find the Kth element in a sorted and rotated array at random point ; '' Set the boundaries for binary search ; '' Apply binary search to find R ; '' Initialize the middle element ; '' Check in the right side of mid ; '' Else check in the left side ; '' Random point either l or h ; '' Return the kth smallest element ; ''Driver Code ; '' Given Input ; '' Function Call
def findkthElement ( arr , n , K ) : NEW_LINE INDENT l = 0 NEW_LINE h = n - 1 NEW_LINE while l + 1 < h : NEW_LINE INDENT mid = ( l + h ) // 2 NEW_LINE if arr [ l ] >= arr [ mid ] : NEW_LINE INDENT l = mid NEW_LINE DEDENT else : NEW_LINE INDENT h = mid NEW_LINE DEDENT DEDENT if arr [ l ] < arr [ h ] : NEW_LINE INDENT r = l NEW_LINE DEDENT else : NEW_LINE INDENT r = h NEW_LINE DEDENT if K <= r + 1 : NEW_LINE INDENT return arr [ r + 1 - K ] NEW_LINE DEDENT else : NEW_LINE INDENT return arr [ n - ( K - ( r + 1 ) ) ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 10 , 8 , 6 , 5 , 2 , 1 , 13 , 12 ] NEW_LINE n = len ( arr ) NEW_LINE K = 3 NEW_LINE print ( findkthElement ( arr , n , K ) ) NEW_LINE DEDENT