File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Can't Find the bug... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Can Watch "Can New topic
Author

Can't Find the bug...

Neil Forrest
Greenhorn

Joined: Apr 03, 2005
Posts: 13
Hi,
Can anyone spot the logic bug in my code? It's a binary search program. I'm timing the search times for different inputs. It works up until the input is n=10^6 on the command line. Then it just keeps running. The longest I've let it go is over 12 hours. What I don't get is that for lesser n values, it's really fast. Memory is not the problem...

public class Binary{
//** declarations of variables
int[] list,list_search;
int size,count;
long time1;
long time2;

//** constructor
public Binary(int n, int k){
size=n;
count=k;
int i;
list=new int[size];
list_search=new int[count];
time1 = 0;
time2 = 0;

//** generate the list of elements
for(i=0;i<size;i++){
list[i]=1+(int)(n*Math.random());
}
for(i=0;i<count;i++)
list_search[i]=1+(int)(n*Math.random());
//sort the list
sort();
//search the element
startsearch();
}

//** sort the list before binary search... done in ascending order
public void sort(){
int i,j,temp;
for(i=0;i<size;i++){
for(j=i;j<size;j++){
if(list[i]>list[j]){
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}
}

//** method for binary search
public void binary(int key){
int low=0;
int high=size-1;
int middle;

while(low<high){
middle=(low+high)/2;
if(key==list[middle])
break;
else if(key<list[middle])
high=middle-1;
else if(key>list[middle])
low=middle+1;

}


}

public void startsearch(){
int i;
time1 = System.currentTimeMillis();
for(i=0;i<count;i++){
binary(list_search[i]);
time2 = System.currentTimeMillis();
}

System.out.println("Search Time: "+ (time2 - time1) +" ms");

}

//** main function
public static void main(String args[]){
int n,k;
if(args.length!=2){
System.out.println("Required number of arguments are not provided");
}
else{
n=Integer.parseInt(args[0]);//parsing the size for number of elements in the list
k=Integer.parseInt(args[1]);// parsing the size of number of elements to be searched
Binary ss =new Binary(n,k);//object created to compare the two search

}
}
}
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

Well, without even looking at the search routine, I can point out that the sort routine's performance will be proportional to n^2. If it takes 1 millisecond to sort 100 items, it will take over 250 hours (!) to sort 1 million items!

You could replace your custom sort routine with a call to one of the sort() functions in the java.util.Arrays() class -- they perform a n ln n -- which is going to make an enormous difference!


[Jess in Action][AskingGoodQuestions]
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
The Java API also contains a binarySearch() method. Of course, if this is a class assignment, there may be some restrictions on what methods you can use from the API. Still, I thought I'd mention it in case you are allowed to use it.

Layne


Java API Documentation
The Java Tutorial
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11229
    
  16

What I don't get is that for lesser n values, it's really fast.

you have discovered one of the classic issues with this kind of sort. It works fantastic for small sets, but just grinds (almost) to a halt as the input set gets bigger.

As you progress in your studies, you will learn some other sorting methods that will speed things up... most of the time. You can find entire books on nothing but searching and sorting (which are closely related). What makes coding fun and interesting is that you can have two completly different sort algorithms. Depending on the input data (and how clever your sorts are), in one case, one sort will be blindingly fast and the other unbearably slow. The other case will cause the exact opposite. result.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Can't Find the bug...