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