Searching

  • Linear Search
     			
    
    
       2  5  3  9  1  7  8  4
    
    
    
    
    
    How many comparisons to find 7?     ______
    
    How many comparisons to find 2?     ______
    
    How many comparisons to find 4?     ______
    
    How many comparisons to not find 6? ______
    
    What is the best case? ___________________ 
    
    What is the worst case? __________________
    
    How many comparisons in average case for list 
    
    with 8 elements?  ______________
    
    
    How many comparisons in average case for list 
    
    with 1,000,000 elements?  _____________
    
    
    
    How many comparisons in average case for list
    
    with n elements?  _______________
    
    How could we improve searching???
    
    
    

  • Binary Search
     			
    
    
       
       1  2  3  4  5  7  8  9
    
    
    
    
    How many comparisons to find 7?     ______
    
    How many comparisons to find 2?     ______
    
    How many comparisons to find 4?     ______
    
    How many comparisons to not find 6? ______
    
    What is the best case? ___________________ 
    
    What is the worst case? __________________
    
    How many comparisons in worst case for list 
    
    with 8 elements?  ______________
    
    
    How many comparisons in worst case for list 
    
    with 1,000,000 elements?  _____________
    
    
    
    How many comparisons in worst case for list
    
    with n elements?  _______________
    
    What is the drawback to this method???
    
    
    
    
    
  • Comparison of Linear and Binary Search
    
    When is it best to use Linear Search? ______________________
    
    
    
    
    
    
    
    When is it best to use Binary Search? ______________________
    
    
    
    
    
    
    
    
  • Linear Search Code
     public static boolean search(int[] array, int toBeFound) {
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    
    
    
  • Binary Search Code
     
    
       
       1  2  3  4  5  7  8  9
     
    
    
     public static boolean search(int[] array, int toBeFound) {
      
        if (array.length == 0)
          return false;
          
        int first = 0;
        int last = array.length - 1;
        int mid;
        
        while (first <= last) {
         
          mid = (last - first)/2 + first;
          
          if (toBeFound == array[mid])
          
            return true;
    	
          else if (toBeFound > array[mid])
          
            first = mid + 1;
    	
          else
          
            last = mid - 1;
         }
         
         return false;
       }
    
    
    What test cases should we use to test the code?