Java Applets Centre
Binary Search


Description
This applet demonstrates the binary search algorithm using a simple array. The algorithm takes O(log n) time in the worst case.


Code (Binary search on a simple array)

boolean binarySearch(int key){
 int first,last,mid = 0;
 boolean found = false;
 first=0; last=size-1;
 while((!found) && (first <= last)){
   mid=first+(last-first)/2;
   if(arr[mid]==key) found=true;
   else if(key < arr[mid]) last=mid-1;
   else if(key > arr[mid]) first=mid+1;
 }
 return found;
}

Data Structures and Algorithms
Java Applets Centre


R. Mukundan
Department of Computer Science
University of Canterbury
Private Bag 4800, Christchurch
New Zealand.