Tech Life On The Way

/*** There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. Solution: 1) linear O(n) two index 2) improved BS O(log(n)) ***/ #include <iostream> using namespace std; int median_linear( int * a , int * b , int asz , int bsz ) {        int a_index = 0, b_index = 0;        int median, index, sz, pre;        median = INT_MIN ;        sz = asz + bsz ;        index = ( asz + bsz )/2;        //edge case - constant time        if ( asz == 0 && bsz != 0) {               if (sz % 2) return b [index];               else return ( b [i...

/*** Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements. Solution: 1) linear O(K) two index 2) improved BS O(log(min(m,n,k))) http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html ***/ #include <iostream> #include <algorithm> using namespace std; // time complexity: O(k), space: O(1) int kth_smallest_linear( int * a , int * b , int asz , int bsz , int k ) {        int a_index = 0, b_index = 0;        int num;        //edge case - constant time        if ( asz == 0) return b [ k -1];        if ( bsz == 0) return a [ k -1];        if ( k == 0 && asz + bsz < k ) return INT_MIN ;   ...