• Our Overall Objective:
  • Learn how to design, implement and analyze algorithms
• A Common Starting Point:
  • Searching for a particular value in a sorted array

• The Approach:
  • Start at the smallest element in the array
  • Iterate through the elements one at a time until the target is found or a larger element is found
• An Implementation:

  •     /**
         * Linear Search
         */
        int search(const int a[], int n, int target)
        {
            int  i;
    
    	i = 0;
    	while ((i < n) && (a[i] < target)) i++;
    
    	if (a[i] == target) return 1;
    	else                return 0;
        }
            

• The Worst Case:
  • When the target is greater than or equal to the largest element in the array
• Worst Case Time Efficiency:
  • The relevant size is the number of elements in the array
  • In the worst case all of the elements in the array must be checked
  • Hence, this algorithm is \(O(n)\)

• The Approach:
  • Start at the smallest element in the array
  • Keep splitting the search space in two until the target is found or until there are no more elements to check
• An Implementation:

  •     /**
         * Binary Search
         */
        int search(const int a[], int n, int target)
        {
            int  i, lower, upper;
    
    	lower = 0;
    	upper = n - 1;
    	i = upper/2;
    
    	while ((lower <= upper) && (a[i] != target))
            {
    	    if (target > a[i]) lower = i + 1;
    	    else          upper = i - 1;
    
    	    i = (lower + upper)/2;
    	}
    
    	if (a[i] == target) return 1;
    	else                return 0;
        }
            

• The Worst Case:
  • When the target is not in the array
• Worst Case Time Efficiency:
  • The relevant size is the number of elements in the array
  • After iteration 1 we have eliminated roughly 1/2 of the elements, after iteration 2 we have eliminated roughly 1/2 + (1/2 * 1/2) = 3/4 of the elements, etc...
  • Generalizing, after iteration \(i\) the portion of remaining elements is roughly given by \((1/2)^{i}\)
  • Assuming that we start with \(n\) elements, this algorithm will terminate when \(n/(2^i) = 1\)
  • In other words, this algorithm will terminate when \(n = (2^i)\)
  • Taking the \(\log_{2}\) of both sides yields \(\log_{2} n = i\)
  • Hence, this algorithm is \(O(\log n)\)

• A Special Case:
  • You know that the biggest integer in the array has a value of \(m-1\) and the smallest has a value of 0
• Why This is Useful:
  • You can create an indicator array with \(m\) elements, that can be used to search through the originl array of \(n\) elements

Setup

    /**
     * One Way to Setup for the Constant Time Search
     */
    int i;
    int a[n], indicator[m];

    .
    .
    .

    for (i=0; i < m; i++)
    {
	indicator[i] = 0;
    }


    for (i=0; i < n; i++)
    {
        indicator[a[i]] = 1;
    }
  

Search

return indicator[a[i]];
  

• Analysis of the Setup Step:
  • If \(n \gt m\) then \(O(n)\) otherwise \(O(m)\)
  • It is sometimes useful to think of this as \(O(m+n)\)
  • Only performed once
• Analysis of the Search:
  • \(O(1)\)

An Alternative Setup Algorithm

    /**
     * Another way to setup for the Constant Time Search
     */
    int i, j, prev;
    int a[n], indicator[m];

    .
    .
    .

    prev = 0;
    for (i=0; i < n; i++)
    {
        for (j=prev; j < a[i]; j++)
        {
	    indicator[j] = 0; // How many times is this done?
	}
        indicator[a[i]] = 1;

        prev = a[i] + 1;      // How many times is this done?
    }