Riaz Ud Din

Ranch Hand

Posts: 34

posted 2 years ago

Hi everyone,

I am studying Java Algorithms online and stuck at line 27 and 28.

Any help would be really appreciated.

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).

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 countint 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).

posted 2 years ago

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

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

viz:

BTW: I'm pretty sure the algorithm could be simplified by making

Winston

- 1

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Riaz Ud Din

Ranch Hand

Posts: 34

posted 2 years ago

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

Winston

- 1

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

Articles by Winston can be found here

posted 2 years ago

You're most welcome.

Winston

Riaz Ud Din wrote:Thanks very much my friend.

You're most welcome.

Winston

Articles by Winston can be found here

Riaz Ud Din

Ranch Hand

Posts: 34

posted 2 years ago

@Winston

Hi again I am abit stuck with line 35 and 39 of the code,

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
posted 2 years ago

Well the easiest way to answer that is: What if

If you didn't have the '

and that could easily cause an infinite loop because the value of

HIH

Winston

- 1

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

Articles by Winston can be found here

It is sorta covered in the JavaRanch Style Guide. |