- Forward


Searching
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • Our Overall Objective:
    • Learn how to design, implement and analyze algorithms
  • A Common Starting Point:
    • Searching for a particular value in a sorted array
Linear Search
Back Forward
  • 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; }
Linear Search (cont.)
Back Forward
  • 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)\)
Binary Search
Back Forward
  • 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; }
Binary Search (cont.)
Back Forward
  • 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)\)
Constant Time Search
Back Forward
  • 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
Constant Time Search (cont.)
Back Forward

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]];
Constant Time Search (cont.)
Back Forward
  • 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)\)
Constant Time Search (cont.)
Back Forward

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? }
There's Always More to Learn
Back -