Thread: find the k'th smallest in two arrays algorithm(psedo code)

i have two arrays ,each of size n, which are sorted.

write an algorithm that finds the k'th smallest amongst the array of size 2n which is the resolt of sticking those two together

in O(lg min (k,2n-k))



i have this idea of how to solve it.





in the added picture

i find the k smallest of array A by A[k] and k smallest of array B by B[k]



and the k smallest of the sum is between those
k1 and k2


in my photo k2>k1



i wrote the following function but i dont know how to know if i got the k'th smallest in the recurtion.and i am not sure abiut the sub arrays ranges in the recursive calls

Code:

Mikum(A,q,r)

k1=A[k/2]

k2=B[k/2]

If (x>y)

Mikum(A,k, n)

Mikum(B,0 ,k)

http://i42.tinypic.com/1192yl5.png

Reposting the same garbage isn't going to make it any clearer...



Why don't you just find the kth smallest in each array and take the smaller of the two?

It sounds like you have two sorted arrays... ok now you need to find, for example, the 8th smallest number in each array... Well if they're sorted that's automatically the 8th element in each.

Then to choose between them you just need something extremely simple like this...

Code:

ksmall = (array1[k] < array2[k]) ? array1[k] : array2[k];

But your definition of the problem is so confused that I'm just guessing.

Commnotater stop posting in this thread


i have two arrays ,each of size n, which are sorted.

write an algorithm that finds the k'th smallest amongst the array of size 2n which is the resolt of sticking those two together

in O(lg min (k,2n-k))



i have this idea of how to solve it.





in the added picture

i find the k smallest of array A by A[k] and k smallest of array B by B[k]



and the k smallest of the sum is between those
k1 and k2


in my photo k2>k1



i wrote the following function but i dont know how to know if i got the k'th smallest in the recurtion.and i am not sure abiut the sub arrays ranges in the recursive calls

Code:

Mikum(A,q,r)

k1=A[k/2]

k2=B[k/2]

If (x>y)

Mikum(A,k, n)

Mikum(B,0 ,k)

http://i42.tinypic.com/1192yl5.png

ok i have reported your posts to the admin

and i will keep posting my question

in the end on top of your trolling posts

It's clear that the OP means concatenating the arrays when s/he demonstrated that the 2 arrays:
1,2,3
and
4,5,5

...could result in:
1,2,3,4,5,6
or
4,5,6,1,2,3

It's not hard to figure out that the arrays are just being concatenated in arbitrary order and that's what s/he means by "sum" or "sticking them together".

There. Mystery solved. Now you can move onto a solution that fits the big-O criteria.

itsme86

the problem is findind the k'smallest in the big 2n array

i know that its between k1 and k2 where k2>k1

so i did recursive calls is the code to look the areas from index of 0 till k1

and another recursive call fron 2n-k

understand?

Nobody can possibly understand what you're tying to do, because your explanations of the problem are so hopelessly nonsensical and confusing, and we told you this. You probably can't write a coherent description of the problem because it is not clear in your own head. Nobody can code a solution to a problem they don't understand. We told you that, too.

What you should have done from that point is take a step back, thought about the problem, tried to understand what the question is. Then you could have come back with a more understandable question and we'd be able to help you.

Instead, what you did is call people stupid, reject their advice, and copy and paste the same pointless incomprehensible crap you've posted from the beginning

We are all volunteers here. We owe you nothing. And that's all you'll get from us with that attitude.



Edit- Wow. You seriously reported Tater to the mods for being a troll? Seriously?

Get lost, henri. Just go away.

What you need...is a crash course in this .

Originally Posted by itsme86

There. Mystery solved. Now you can move onto a solution that fits the big-O criteria.

AFAIK....
This is a merge sort... after deciding in which direction to do it.