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;

//** 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

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!

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.

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