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

• 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!

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