• Post Reply Bookmark Topic Watch Topic
  • New Topic

Median of Two Sorted Arrays  RSS feed

 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ 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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks very much my friend.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Riaz Ud Din wrote:Thanks very much my friend.

You're most welcome.

Winston
 
Riaz Ud Din
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@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: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Winston Thanks very much. You are a life saver.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!