Broke out a core "find target index" alg and adapted to Median problem


  • 0
    D

    I thought I'd try out finding a somewhat more general-purpose algorithm and then adapting that to this specific problem. The general alg. is: "given 2 sorted arrays, find an index into each that corresponds to a given target index into the merged version". Below is my implementation of that alg (in C++);

            // Find indicies in each array to correspond to the target index of the unified array.
            int i1,i2;
            int lo = 0;
            int hi = nums1.size();
            while( lo <= hi ) {
                i1 = (lo + hi) / 2;
                i2 = target - i1;
                cout<< "Trying i1="<<i1<< " i2="<<i2 <<endl;
                // Conditions we must satisfy with i1, i2 at the target index:
                //   1. (all values in nums1 below i1) <= (all values in nums2 at or above i2)
                //   2. (all values in nums2 below i2) <= (all values in nums1 at or above i1)
                // This translates to rules:
                //   1. nums1[i1-1] <= nums2[i2]  OR  i1 <= 0  OR  i2 >= nums2.size()
                //   2. nums2[i2-1] <= nums1[i1]  OR  i2 <= 0  OR  i1 >= nums1.size()
                // If (1) fails, then i1 needs to decrease, and i2 increase accordingly.
                // If (2) fails, i1 should increase and i2 decrease.
                if ( i1 > 0  &&  i2 < nums2.size() && nums1[i1-1] > nums2[i2] ) {
                    // Rule 1 fails: i1 needs to increase, so update
                    //   lower bound to one higher than current i1 value.
                    hi = i1 - 1;
                    cout<< "  - rule 1 fails: nums1[i1-1]="<<nums1[i1-1]<<
                        " > nums2[i2]="<< nums2[i2]<> " -- decrease i1: hi="<<hi <<endl;
                }
                else if ( i2 > 0  &&  i1 < nums1.size() && nums2[i2-1] > nums1[i1] ) {
                    // Rule 2 fails: increase i1; update upper bound.
                    lo = i1 + 1;
                    cout<< "  - rule 2 fails: nums2[i2-1]="<<nums2[i2-1]<<
                        " > nums1[i1]="<< nums1[i1]<< " - increase i1: lo="<<lo <<endl;
                }
                else {
                    // both rules passed.  Done.
                    cout<< "  - both rules passed.\n";
                    break;
                }
            }
            cout<< "Result i1="<<i1<< " i2="<<i2<< endl;
    

    Selecting the target is just finding the "lower" of the 2 possible "median" indicies (so (m+n-1)/2 ). The code to find the median from the resulting i1 and i2 is fairly verbose, as it still has to deal with a lot of corner cases, so I'm not bothering to post it.

    This is not the most concise way to do this by a long shot, but it was a little easier for me to understand this way, and could be more useful in my "toolbox." going forwards. :)

    Thanks to stellari for his post & explanation; it really helped clarify my thinking on this!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.