Tech Life On The Way

/*** find median of rotated sorted array. O(logn) ***/ #include <iostream> using namespace std; int find_start( int * a , int st , int ed ) {        if ( st >= ed ) return st ;        int mid = ( st + ed ) / 2;        if ( a [mid] < a [mid-1]) return mid;        if ( a [mid] > a [ ed ]) {               return find_start( a , mid+1, ed );        } else {               return find_start( a , st , mid-1);        } } int get_median( int * a , int sz ) {        int m = sz /2;        int id = find_start( a , 0, sz -1);     ...

/*** 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...