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

Printable View

• 04-15-2008, 09:24 PM
fireball2008
how 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 AM
sukatoa
What have you done so far!!!!

kind regards,
sukatoa
• 04-16-2008, 11:24 AM
Eranga
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 PM
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.
• 04-17-2008, 03:41 PM
sukatoa
Take a look at this....

Have some experiments on it,

update us,
sukatoa
• 04-18-2008, 04:48 AM
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;     } }```
• 04-18-2008, 05:09 PM
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?
• 04-21-2008, 03:44 AM
Eranga
Quote:

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:

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?
• 04-22-2008, 03:21 AM
fireball2008
Quote:

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.