|
|
Welcome to the Java Forums.
You are currently viewing our boards as a guest which gives you limited access to view most discussions and access our other features. By joining our free community, you will:
- have access to post topics
- communicate privately with other members (PM)
- not see advertisements between posts
- have the possibility to earn one of our surprises if you are an active member
- access many other special features that will be introduced later.
Registration is fast, simple and absolutely free so please, join our community today!
If you have any problems with the registration process or your account login, please contact us.
|
|

04-15-2008, 11:24 PM
|
|
Member
|
|
Join Date: Apr 2008
Posts: 28
|
|
|
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, 01:06 PM
|
 |
Senior Member
|
|
Join Date: Jan 2008
Location: Cebu City, Philippines
Posts: 527
|
|
|
What have you done so far!!!!
kind regards,
sukatoa
|
|

04-16-2008, 01:24 PM
|
 |
Moderator
|
|
Join Date: Jul 2007
Location: Colombo, Sri Lanka
Posts: 4,610
|
|
|
Yes, using binary search you can find the union of two arrays. So, as sukatoa says, what you have done up to now?
__________________
Use an appropriate Subject. "Help, urgent!" isn't one. To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
Has someone helped you? Then you can To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts. their helpful post.
Want to make your IDE the best? To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
|

04-16-2008, 11:04 PM
|
|
Member
|
|
Join Date: Apr 2008
Posts: 28
|
|
|
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, 05:41 PM
|
 |
Senior Member
|
|
Join Date: Jan 2008
Location: Cebu City, Philippines
Posts: 527
|
|
Take a look at this....
Have some experiments on it,
update us,
sukatoa
|
|

04-18-2008, 06:48 AM
|
 |
Moderator
|
|
Join Date: Jul 2007
Location: Colombo, Sri Lanka
Posts: 4,610
|
|
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 
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;
}
}
__________________
Use an appropriate Subject. "Help, urgent!" isn't one. To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
Has someone helped you? Then you can To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts. their helpful post.
Want to make your IDE the best? To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
|

04-18-2008, 07:09 PM
|
|
Member
|
|
Join Date: Apr 2008
Posts: 28
|
|
|
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, 05:44 AM
|
 |
Moderator
|
|
Join Date: Jul 2007
Location: Colombo, Sri Lanka
Posts: 4,610
|
|
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.
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?
__________________
Use an appropriate Subject. "Help, urgent!" isn't one. To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
Has someone helped you? Then you can To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts. their helpful post.
Want to make your IDE the best? To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
|
|

04-22-2008, 05:21 AM
|
|
Member
|
|
Join Date: Apr 2008
Posts: 28
|
|
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.
|
|
| Thread Tools |
|
|
| Display Modes |
Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|