Computer Science Canada :: View topic - timing sequential search vs binary search

public static void generate(int list1 []){
for (int i=0;i<list1.length;i++ ){
list1[i]=(int)(Math.random()*100+1);
}
   }

public static int sequentialSearch(int list1[], int key) {

for (int k = 0; k < list1.length; k++)

if (list1[k] == key)
return k;

return -1; // Failure if this is reached
} // sequentialSearch()

public static int binarySearch(int list1[], int key) {
int low = 0; // Initialize bounds
int high = list1.length-1;
while (low <= high) { // While not done
int mid = (low + high) / 2;
if (list1[mid] == key)
return mid; // Success
else if (list1[mid] < key)
low = mid + 1; // Search top half
else
high = mid - 1; // Search bottom half
} // while
return -1; // Post condition: low > high implies search failed
} // binarySearch()

public static void main(String[] args) {
int[] list1 = new int[10000];
long starttime;
   starttime = System.currentTimeMillis();
   long endtime = 0;
   endtime = System.currentTimeMillis();

   generate (list1);
   starttime = System.currentTimeMillis();
   System.out.println (sequentialSearch (list1, 20));
   endtime = System.currentTimeMillis();
   System.out.print ("time needed for sequential search: ");
   System.out.println(endtime - starttime);


   generate (list1);
   starttime = System.currentTimeMillis();
   System.out.println (binarySearch(list1,100));
   endtime = System.currentTimeMillis();
   System.out.print("time needed for binary search ");
   System.out.println(endtime - starttime);

}

}

Author:	rated [ Sun Jan 25, 2009 4:13 pm ]
Post subject:	RE:timing sequential search vs binary search
the parameters do not need to be the same, do they?

Author:	Clayton [ Sun Jan 25, 2009 5:35 pm ]
Post subject:	RE:timing sequential search vs binary search
Well, you're trying to pass an array of integers are you not? I don't see that reflected in your parameters.

Author:	DemonWasp [ Mon Jan 26, 2009 9:14 am ]
Post subject:	RE:timing sequential search vs binary search
I see a couple of problems here. First, you need to sort the array before passing it to a binary sort. Sequential sorts work on unsorted data; binary sorts only work on sorted data. Second, you need to realise that "binary search is faster than sequential search" doesn't mean that one is noticeably faster than the other; the important difference is what happens if you have to do the search a large number of times (say a million or more). Don't forget to include the time required to sort the array into the execution time of the binary search. It may be true that for few enough executions, sequential search is faster than binary search, since you don't have the high initial cost of the sort beforehand.