Results 1 to 9 of 9
  1. #1
    fireball2008 is offline Member
    Join Date
    Apr 2008
    Posts
    28
    Rep Power
    0

    Default 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.

  2. #2
    sukatoa's Avatar
    sukatoa is offline Senior Member
    Join Date
    Jan 2008
    Location
    Cebu City, Philippines
    Posts
    556
    Rep Power
    7

    Default

    What have you done so far!!!!

    kind regards,
    sukatoa

  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

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

  4. #4
    fireball2008 is offline Member
    Join Date
    Apr 2008
    Posts
    28
    Rep Power
    0

    Default

    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.

  5. #5
    sukatoa's Avatar
    sukatoa is offline Senior Member
    Join Date
    Jan 2008
    Location
    Cebu City, Philippines
    Posts
    556
    Rep Power
    7

    Default

    Take a look at this....

    Have some experiments on it,

    update us,
    sukatoa

  6. #6
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    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 ;)

    Java 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;
        }
    }

  7. #7
    fireball2008 is offline Member
    Join Date
    Apr 2008
    Posts
    28
    Rep Power
    0

    Default

    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?

  8. #8
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by fireball2008 View Post
    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 View Post

    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?

  9. #9
    fireball2008 is offline Member
    Join Date
    Apr 2008
    Posts
    28
    Rep Power
    0

    Default

    Quote Originally Posted by Eranga View Post
    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.

Similar Threads

  1. Replies: 2
    Last Post: 09-22-2011, 09:48 PM
  2. Could not find the main class, program will exit.
    By aryubi in forum New To Java
    Replies: 39
    Last Post: 02-19-2010, 10:02 AM
  3. Replies: 0
    Last Post: 04-14-2008, 08:39 PM
  4. Find nth root of a number
    By perito in forum New To Java
    Replies: 1
    Last Post: 03-03-2008, 06:51 AM
  5. Replies: 1
    Last Post: 02-16-2008, 09:10 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •