Search Algorithms

From Java Programming II
Jump to: navigation, search

Linear Search

Binary Search

Code

 public class ArraySearch {
    
    public static int linearSearch(int [] A, int key){
        int numberOfOperations =0;
        int position = -1;
        for (int i = 0; i<A.length; i++){
            numberOfOperations++;
            if (A[i]==key){
                position=i;
                break;//exit the for loop
            }
        }
        System.out.println("Number of operations (Linear Search) = "+numberOfOperations);
        return position;
    }
    
    public static int binarySearch(int [] A,int key){
        
        int numberOfOperations =0;
        
        int middle_index = A.length/2;
        int low_index = 0;
        int high_index=A.length-1;
        int position = -1;
        
        do{
            numberOfOperations++;
            if (key == A[middle_index]){
                position = middle_index;
            } 
            else if (key<A[middle_index])
                    high_index = middle_index-1; 
            else
                    low_index = middle_index+1;
            
         middle_index = (high_index+low_index+1)/2;
            
        }while((high_index>=low_index)&&(position==-1));
        
        System.out.println("Number of operations (Binary Search) = "+numberOfOperations);
        return position;
    }
    
   public static void main (String []args){
       
       int max_value = 500000000;
       //create and declare the array
       int [] array = new int [max_value];
       
       //populate the array in increasing order
        for (int i = 0; i<max_value; i++){
            array[i]=i; 
        }
        
        int searchValue = max_value-1;
       
       long t0= System.currentTimeMillis();
       int location = linearSearch(array, searchValue);
       long t1= System.currentTimeMillis();
       
       System.out.printf("Linear Search \n\t Linear search time: %d ms\n\tLocation: %d\n", (t1-t0), location);
        
       long t2= System.currentTimeMillis();
       location = binarySearch(array,searchValue);
       long t3= System.currentTimeMillis();
       System.out.printf("Binary Search \n\tLinear search time: %d ms\n\tLocation: %d\n", (t3-t2), location);
 
   }
    
 }