Sequential and Binary Search
Chapter 18
Introduction
Objectives
After the next two lectures and labs, you will be able to:
Implement the sequential and binary search algorithms.
Explain how these search algorithms perform.
State lower bound on comparison-based search algorithms.
Implement various sorting algorithms.
Use the asymptotic notation, Big-
, to analyze these algorithms’ performance.
With a Search Algorithm, you can:
Determine whether a particular item is in an array or list.
If the data is specially organized (for example, sorted), find the location in the list where a new item can be inserted.
Find the location of an item to be deleted.
Search Algorithm Terminology
An item’s key – a special member that uniquely identifies the item in the data set.
A key comparison – comparing the key of the search item with the key of an item in the list.
- We can count the number of key comparisons as a measure of performance.
The key that we are searching for is called the target or search item.
Sequential Search
Sequential Search (a.k.a. Linear Search)
Same for both array-based and linked lists.
Starts at the first element and examines each element until a match is found.
Can be implemented iteratively (using a loop) or recursively.
template <typename Type>
unsigned int sequentialSearch(const Type array[],
unsigned int size, const Type& key)
{
unsigned int index;
// Iterate until we find the key or reach the end of the array
for (index = 0; index < size && array[index] != key; ++index)
{
}
// If we found the key, return the index, otherwise return UINT_MAX
return index < size ? index : UINT_MAX;
}template <typename Type>
unsigned int sequentialSearchRecursive(const Type array[],
unsigned int size, const Type& key)
{
unsigned int index;
// Base case, empty list
if (size == 0)
{
index = UINT_MAX;
}
// Base case, key found in first location
else if (array[0] == key)
{
index = 0;
}
// Recursive case, run these checks again with a smaller array.
else
{
// Call ourself
index = sequentialSearchRecursive(array + 1, size - 1, key);
if (index != UINT_MAX)
++index;
}
return index;
}Key Comparisons of a Sequential Search
Remember, the speed of a computer does not affect the number of key comparisons required.
Statements before and after the loop are executed only once,
. Statements in the while loop repeated some number from 1 to
times (where is the number of keys). If the search key is not in the list, there will be
comparisons. In the best case, the first key matches the search item with just one comparison.
In the worst case, the target is not in the list, so there will be
comparisons. Average number of comparisons:
Binary Search (for Sorted Lists)
Binary search can be applied to sorted arrays.
Uses the “divide and conquer” technique.
Steps
First, compare the target to the middle element.
If the search item is less than the middle element, restrict the search to the lower half of the list.
Otherwise, restrict the search to the upper half of the list.
Repeat until found.
Find the location of 75 in this sorted array.
The Performance of the Binary Search on Arrays
Every iteration cuts the size of the search list in half.
If list
has items, at most iterations are needed to find . Every iteration makes two key comparisons.
For
, binary search has at most key comparisons. Max number of comparisons =
. The sequential search required
key comparisons (average) to find if is in .
Asymptotic Notation (Big-O Notation)
After an algorithm is designed, it should be analyzed.
There are often various ways to design a particular algorithm.
Certain algorithms take very little computer time to execute.
Others take a considerable amount of time.
| 1 | 0 | 0 | 1 | 2 |
| 2 | 1 | 2 | 4 | 4 |
| 4 | 2 | 8 | 16 | 16 |
| 8 | 3 | 24 | 64 | 256 |
| 16 | 4 | 64 | 256 | 65,536 |
| 32 | 5 | 160 | 1,024 | 4,294,967,296 |
| 64 | 6 | 384 | 4,096 | 1.84467e+19 |
Let
be a function of . Asymptotic: the study of the function
as becomes larger and larger without bound. Let
and be real-valued, non-negative functions. is Big-O of , written if there are constants and such that
Growth Rate
| 10 | 100 | 160 |
| 50 | 2,500 | 2,720 |
| 100 | 10,000 | 10,420 |
| 1,000 | 1,000,000 | 1,0004,020 |
| 10,000 | 100,000,000 | 100,040,020 |
| 100,000 | 10,000,000,000 | 10,000,400,020 |
Growth Rate Functions
| Function | Growth rate of |
|---|---|
| Constant (is independent of the problem’s size). | |
| Logarithmic (increases increases slowly as the problem size increases). | |
| Linear (increases directly with the size of the problem). | |
| Quadratic (increases rapidly with the size of the problem). | |
| Cubic (increases more rapidly with the size of the problem than the time requirement for a quadratic algorithm). | |
| Exponential (too rapid to be practical, as the size of the problem increases). |
Comparing Sequential and Binary Search
| Algorithm | Successful Search | Unsuccessful Search |
|---|---|---|
| Sequential Search | ||
| Binary Search |
The number of comparisons for a list of length
Lower Bound on Comparison-Based Search
Comparison-based search algorithms: Search a list by comparing the target element with list elements.
Theorem: Let
Corollary: The binary search algorithm is an optimal worst-case algorithm for solving search problems by the comparison method. From these results, it follows that if we want to design a search algorithm that is of an order less than
Sorting Algorithms
To compare the performance of commonly used sorting algorithms, one must provide some analysis of these algorithms.
These sorting algorithms can be applied to either array-based lists or linked lists.