db
BAN USERDoing binary search.
Complexity: O(log N), where N is the size of array data
int getNth(int a[], int size_a,
int b[], int size_b,
int k) {
if(size_a + size_b < k || k <= 0) {
throw "Not found";
}
int left_a = 0;
int right_a = (k < size_a) ? k : size_a;
do {
// pivots go from 0, 1...N
// 0 - dont include any element from that array
// 1 - first element of the array
// Hence, you will notice that all array references are left shifted by 1
int pivot_a = left_a + (right_a - left_a) / 2;
int pivot_b = k - pivot_a;
// Second array is smaller than "k"
if(pivot_b > size_b) {
left_a = (left_a == size_b) ? size_b + 1 : size_b;
continue;
}
if(pivot_a == 0 && left_a == right_a) {
return b[k-1];
}
if(pivot_b == 0) {
return a[k-1];
}
// We have found the expected element when:
// element pointed by a pivot is less than or equal to all elements of the other array
// Example with k = 5
// 1,3,5,7,9
// 2,4,6,8,10
// when pivot_a = 3 and pivot_b = 2
// (a[pivot_a-1]=5) is less than (b[pivot_b]=6)
// and
// (b[pivot_b-1]=2) is less than (a[pivot_a]=5)
if(pivot_b == size_b || a[pivot_a-1] <= b[pivot_b]) {
if(pivot_a == size_a || b[pivot_b-1] <= a[pivot_a]) {
return (a[pivot_a-1] > b[pivot_b-1]) ? a[pivot_a-1] : b[pivot_b-1];
}
else {
left_a = pivot_a + 1;
}
}
else {
right_a = pivot_a;
}
}
while(1);
}
Doubt that a O(log n) solution can be given for this problem, unless the BST is balanced probably?
Worst case, take a BST that is build completely with just the right tree
Example:
In order to find the 6th element, we have to traverse through down the right chain and we will have a complexity of O(n).
- db December 07, 2014