Results 1 to 9 of 9
 04152008, 09:24 PM #1Member
 Join Date
 Apr 2008
 Posts
 28
 Rep Power
 0
 04162008, 11:06 AM #2
What have you done so far!!!!
kind regards,
sukatoa
 04162008, 11:24 AM #3
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 20
Yes, using binary search you can find the union of two arrays. So, as sukatoa says, what you have done up to now?
 04162008, 09:04 PM #4Member
 Join Date
 Apr 2008
 Posts
 28
 Rep Power
 0
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.
 04172008, 03:41 PM #5
Take a look at this....
Have some experiments on it,
update us,
sukatoa
 04182008, 04:48 AM #6
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 20
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; } }
 04182008, 05:09 PM #7Member
 Join Date
 Apr 2008
 Posts
 28
 Rep Power
 0
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?
 04212008, 03:44 AM #8
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 20
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?
 04222008, 03:21 AM #9Member
 Join Date
 Apr 2008
 Posts
 28
 Rep Power
 0
Similar Threads

Error: Could Not Find Main Class. Program Will Exit
By silvia in forum New To JavaReplies: 2Last Post: 09222011, 09:48 PM 
Could not find the main class, program will exit.
By aryubi in forum New To JavaReplies: 39Last Post: 02192010, 11:02 AM 
Sorting, Searching, and Inserting into a sorted array
By Java Tip in forum java.langReplies: 0Last Post: 04142008, 08:39 PM 
Find nth root of a number
By perito in forum New To JavaReplies: 1Last Post: 03032008, 07:51 AM 
Recursive Method ==> find minimum value from array
By NatNat in forum New To JavaReplies: 1Last Post: 02162008, 10:10 PM
Bookmarks