K | Python3 program to find kth element from two sorted arrays ; In case we have reached end of array 1 ; In case we have reached end of array 2 ; k should never reach 0 or exceed sizes of arrays ; Compare first elements of arrays and return ; Size of array 1 is less than k / 2 ; Last element of array 1 is not kth We can directly return the ( k - m ) th element in array 2 ; Size of array 2 is less than k / 2 ; Normal comparison , move starting index of one array k / 2 to the right ; Driver code
def kth ( arr1 , arr2 , m , n , k , st1 = 0 , st2 = 0 ) : NEW_LINE INDENT if ( st1 == m ) : NEW_LINE INDENT return arr2 [ st2 + k - 1 ] NEW_LINE DEDENT if ( st2 == n ) : NEW_LINE INDENT return arr1 [ st1 + k - 1 ] NEW_LINE DEDENT if ( k == 0 or k > ( m - st1 ) + ( n - st2 ) ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( k == 1 ) : NEW_LINE INDENT if ( arr1 [ st1 ] < arr2 [ st2 ] ) : NEW_LINE INDENT return arr1 [ st1 ] NEW_LINE DEDENT else : NEW_LINE INDENT return arr2 [ st2 ] NEW_LINE DEDENT DEDENT curr = int ( k / 2 ) NEW_LINE if ( curr - 1 >= m - st1 ) : NEW_LINE INDENT if ( arr1 [ m - 1 ] < arr2 [ st2 + curr - 1 ] ) : NEW_LINE INDENT return arr2 [ st2 + ( k - ( m - st1 ) - 1 ) ] NEW_LINE DEDENT else : NEW_LINE INDENT return kth ( arr1 , arr2 , m , n , k - curr , st1 , st2 + curr ) NEW_LINE DEDENT DEDENT if ( curr - 1 >= n - st2 ) : NEW_LINE INDENT if ( arr2 [ n - 1 ] < arr1 [ st1 + curr - 1 ] ) : NEW_LINE INDENT return arr1 [ st1 + ( k - ( n - st2 ) - 1 ) ] NEW_LINE DEDENT else : NEW_LINE INDENT return kth ( arr1 , arr2 , m , n , k - curr , st1 + curr , st2 ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( arr1 [ curr + st1 - 1 ] < arr2 [ curr + st2 - 1 ] ) : NEW_LINE INDENT return kth ( arr1 , arr2 , m , n , k - curr , st1 + curr , st2 ) NEW_LINE DEDENT else : NEW_LINE INDENT return kth ( arr1 , arr2 , m , n , k - curr , st1 , st2 + curr ) NEW_LINE DEDENT DEDENT DEDENT arr1 = [ 2 , 3 , 6 , 7 , 9 ] NEW_LINE arr2 = [ 1 , 4 , 8 , 10 ] NEW_LINE k = 5 NEW_LINE print ( kth ( arr1 , arr2 , 5 , 4 , k ) ) NEW_LINE