Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Can't Find the bug...

 
Neil Forrest
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12097
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic