Problem:
Given two sorted arrays A and B of length n, find the kth smallest element in the union of the two sorted arrays. Do so in Θ(lgn).
Complexity:
O(log N)
Code:
Popular Posts
-
Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ... -
Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
-
Problem: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
-
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.... -
How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
-
Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
-
Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
-
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
-
Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
-
Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...
