how to right a program that find kth number in two sorted array?

[fireball2008]

There is two sorted array A, and B, how to write a program that runs in log(n)^2 that compute the kth value in the union of this two array.
Any idea is welcome.
I know it has something to do with using binary search.

[sukatoa]

What have you done so far!!!!

kind regards,
sukatoa

[Eranga]

Yes, using binary search you can find the union of two arrays. So, as sukatoa says, what you have done up to now?

[fireball2008]

I only know how to do it in linear time, I have no idea how to do it in log(n)^2
for linear time:
public int find(int k, int j, int i){
int temp = A[i]
int temp2 = B[j]
if(A[i]>B[j])
j++;
else
i++;
if((i+j)==k)
{if(A[i]>B[j])
return A[i];
else
return B[j];}
else
return find(k, i, j);}}

call find(k, 0, 0);

but that is linear time I need log(n)^2 time.

[sukatoa]

Take a look at this....

Have some experiments on it,

update us,
sukatoa

[Eranga]

For sorted array you can make a simple binary search as follows. I've try it and seems working fine. But you have to use a sorted array

Code:

public class BunarySearch {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int[] myArray = {1, 3, 5, 6, 8};
        System.out.println("5 is found at " + binarySearch(myArray, 8));
    }

    private static int binarySearch(int[] array, int lookFor) {
        
        int high = array.length;
        int low = -1;
        int temp;
        
        while((high - low) > 1) {
            temp = (high + low) >>> 1;
            if(array[temp] > lookFor) {
                high = temp;
            }
            else {
                low = temp;
            }
        }
        if(low == -1 || array[low] != lookFor)
            return -1;
         else
            return low;
    }
}

[fireball2008]

I know the binary search, but how to search two arrays at same time without combine the elements together.


I think I got some ideas

first pick a value in array A and note down it's index, and binary search in array B.
and some how the returning index of B + index of A = K, if this is true, then return the larger element is that right?

[Eranga]

Quote:

Originally Posted by fireball2008

I know the binary search, but how to search two arrays at same time without combine the elements together.

why don't you impossible. I mean If you know the binary search, as I do select the comparing value form one array and do the binary search with other array. Do it for the length of the first array.

Quote:

Originally Posted by fireball2008

first pick a value in array A and note down it's index, and binary search in array B.
and some how the returning index of B + index of A = K, if this is true, then return the larger element is that right?

You are adding index of two array elements, then what is variable K?

[fireball2008]

Quote:

Originally Posted by Eranga

why don't you impossible. I mean If you know the binary search, as I do select the comparing value form one array and do the binary search with other array. Do it for the length of the first array.

but would that run in n log n runtime. each array has n elements. I need (log n)^2 runtime.