programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Rob Spoor
• Tim Cooke
• Junilu Lacar
Sheriffs:
• Henry Wong
• Liutauras Vilda
• Jeanne Boyarsky
Saloon Keepers:
• Jesse Silverman
• Tim Holloway
• Stephan van Hulst
• Tim Moores
• Carey Brown
Bartenders:
• Al Hobbs
• Mikalai Zaikin
• Piet Souris

# Median of Two Sorted Arrays

Ranch Hand
Posts: 34
• • Number of slices to send:
Optional 'thank-you' note:
• • Hi everyone,
I am studying Java Algorithms online and stuck at line 27 and 28.
Any help would be really appreciated.

int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count

I don't understand the formulas for calculating aMid, and bMid. What's the logic behind these formulas?
Here is the link to program.

http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/

Following is the code.

I got some idea, from the comments with the code, how these formulas are calculated but still don't understand to explain to someone "why these formulas" Or what's the logic behind of these formulas?

For int aMid = aLen * k / (aLen + bLen); // a's middle count

As aMid = aLen / 2 --(i)

and k = （aLen + bLen)/2, -->2 = (aLen + bLen)/k

putting value of 2 in equ (i)

so aMid = aLen/(aLen + bLen)/k== aLen *k/ (aLen+bLen)

and for int bMid = k - aMid - 1; // b's middle count

aMid + bMid + 1 = k must be satisfied to be able to make the conclusions it does when A[aMid] > B[bMid]

As for why aMid + bMid + 1 = k is significant: If A[aMid] is greater than B[bMid], you know that any elements in after A[aMid] in A can't be the kth element since there are too many elements in B lower than it (and would exceed k elements). You also know that B[bMid] and any element before B[bMid] in B can't be the kth element since there are too few elements in A lower than it (there wouldn't be enough elements before B[bMid] to be the kth element).

Bartender Posts: 10780
71   • 1
• • Number of slices to send:
Optional 'thank-you' note:
• • Riaz Ud Din wrote:I don't understand the formulas for calculating aMid, and bMid. What's the logic behind these formulas?
...
For int aMid = aLen * k / (aLen + bLen); // a's middle count

Well, I can't tell you exactly why - although if you look at the excellent explanation for solution 2, you'll see the general concept behind it.

What I can tell you is that the above formula ensures that aMid always lies within the bounds of A, no matter how disparate the two lengths are.

For example, suppose that aLen is 1 and bLen is 5. The initial value for k would then be 3, which is outside the bounds of A, but multiplying it by aLen and then dividing it by aLen + bLen ensures that the result will always be less then aLen.

viz: (1 * 3) / (1 + 5) == 0 (integer division remember)

BTW: I'm pretty sure the algorithm could be simplified by making aEnd and bEnd exclusive rather than inclusive. It saves a lot of those '+ 1's and '- 1's (old C trick).

Winston

Riaz Ud Din
Ranch Hand
Posts: 34
• • Number of slices to send:
Optional 'thank-you' note:
• • @ Winston Gutkowski
Thanks very much. Your explanation is awesome and it makes sense. I got it now.
Can you please guide me how to make the algorithm simplified by making aEnd and bEnd exclusive rather than inclusive.

Winston Gutkowski
Bartender Posts: 10780
71   • 1
• • Number of slices to send:
Optional 'thank-you' note:
• • Riaz Ud Din wrote:Can you please guide me how to make the algorithm simplified by making aEnd and bEnd exclusive rather than inclusive.

I thought you might ask me that. Basically, you just add 1 to them, viz:Lines 36 and 40 I'm not absolutely sure about. I don't think they need to be changed, because you've already ruled out aMid or bMid as being part of your "next" array, but I could be wrong.

Winston

Riaz Ud Din
Ranch Hand
Posts: 34
• • Number of slices to send:
Optional 'thank-you' note:
• • Thanks very much my friend.

Winston Gutkowski
Bartender Posts: 10780
71   • • Number of slices to send:
Optional 'thank-you' note:
• • Riaz Ud Din wrote:Thanks very much my friend.

You're most welcome.

Winston

Riaz Ud Din
Ranch Hand
Posts: 34
• • Number of slices to send:
Optional 'thank-you' note:
• • @Winston
Hi again I am abit stuck with line 35 and 39 of the code, k = k - (bMid - bStart + 1); As (A[aMid] > B[bMid]) so all the values before bMid + bMid itself can't be K so subtract it from K but why 1 is added? I am totally confused about 1. Your help will be very much appreciated. Thanks in advance

Winston Gutkowski
Bartender Posts: 10780
71   • 1
• • Number of slices to send:
Optional 'thank-you' note:
• • Riaz Ud Din wrote:@Winston
Hi again I am abit stuck with line 35 and 39 of the code, k = k - (bMid - bStart + 1); As (A[aMid] > B[bMid]) so all the values before bMid + bMid itself can't be K so subtract it from K but why 1 is added? I am totally confused about 1.

Well the easiest way to answer that is: What if bMid and bStart are both the same value (in particular: 0)?

If you didn't have the '+ 1' in there, you'd have
k = k - (bMid - bStart) == k = k - (n - n) == k = k - 0 == k
and that could easily cause an infinite loop because the value of k hasn't changed.

HIH

Winston

Riaz Ud Din
Ranch Hand
Posts: 34
• • Number of slices to send:
Optional 'thank-you' note:
• • @Winston Thanks very much. You are a life saver. 