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.

- 04-15-2008, 09:24 PMfireball2008how to right a program that find kth number in two sorted array?
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. - 04-16-2008, 11:06 AMsukatoa
What have you done so far!!!!

kind regards,

sukatoa - 04-16-2008, 11:24 AMEranga
Yes, using binary search you can find the union of two arrays. So, as sukatoa says, what you have done up to now?

- 04-16-2008, 09:04 PMfireball2008
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. - 04-17-2008, 03:41 PMsukatoa
Take a look at this....

Have some experiments on it,

update us,

sukatoa - 04-18-2008, 04:48 AMEranga
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;

}

}

- 04-18-2008, 05:09 PMfireball2008
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? - 04-21-2008, 03:44 AMEranga
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.

You are adding index of two array elements, then what is variable K? - 04-22-2008, 03:21 AMfireball2008