CSC 150 : Search Algorithms
primary information resource: An Invitation to Computer Science, G. Michael Schneider and Judith L. Gersting, Brooks/Cole, 2000.

[ back to chapter 3 | schedule | on to sort | on to chapter 4 ]

Analysis of sequential search algorithm (Figure 3.1) from lab 2.

Recall that you counted steps as part of lab 2.
Using Figure 3.1 as reference, “count steps” for the case where n=1000 and NAME is equal to the 250th name on the list.
Step 1: 1
Step 2: 1
Step 3: 250
Step 4: 250
Step 5: 1
Step 6: 1
Step 7: 249
Step 8: 1
Step 9: 0
Step 10: 1

How would the counts change if NAME matched the first name on the list?
How would the counts change if NAME matched the last name on the list?
How would the counts change if NAME were not matched in the list?
How many “steps” does this algorithm require?  Which test case(s) should you base your answer on?
Which is the best case scenario (fastest time), worst?  average?
Which steps are significant?
What is the order of magnitude of this algorithm (best, worst, average)?

Breaking the barrier usually requires a “divide and conquer” approach.

How do you find someone in the phone book?  Sequential search?  I’ll bet not!  Why not?  What allows you to cut directly into the “middle” of the book?

Suppose your search algorithm could assume the list was already sorted.  How could you take advantage of this to speed up the search?

Compare target value to value in middle position:
If target == middle, search is over!
If target < middle, value must be in first half (if at all)
If target > middle, value must be in second half (if at all)

By comparing target to one value, it cuts search space in half!  Contrast this to sequential search – how much is search space reduced by one comparison?

Suppose target < middle, what next?
Repeat the search using first half (sublist) only.
Continue in this fashion until either the match is found or the search space is empty.

EXAMPLE

Target: 33
List:   4   7   12    18    25     32     33   40   44

Comparison 1
List:   4   7   12    18    25     32     33   40   44
Middle value: 25
33 > 25 so target must be in second half.

Comparison 2
Sublist:   32     33   40   44
Middle value: 23
33 == 33 so target is found!

EXAMPLE

Target: 17
List:   4   7   12    18    25     32     33   40   44

Comparison 1
List:   4   7   12    18    25     32     33   40   44
Middle value: 25
17 < 25 so target must be in first half.

Comparison 2
Sublist:   4   7   12    18
Middle value: 7
17 > 7 so target must be in second half.

Comparison 3
Sublist:  12  18
Middle value: 12
17 > 12 so target must be in second half

Comparison 4
Sublist: 18
Middle value: 18
17 < 18 so target must be in first half

First half is empty, so target not found.
 

Runtime analysis of binary search.
How many comparisons are done?
Any difference between worst and best case for comparisons? Yes
What is the best case?  Target is equal to middle value in original list
What is the worst case? Target is not in the list.
Best case comparisons?
Worst case comparisons?  (see below)
 

Computing worst case order of magnitude

• How many times can you cut something, such as list length, in half (using integer division) before it is reduced to nothing?
• If original list is length 8, sublists are 4, 2, 1.
• If original list is length 16, sublists are 8, 4, 2, 1.
• If original list is length 1024, sublists are 512, 256, 128, 64, 32, 16, 8, 4, 2, 1.
• Worst case requires 2 comparisons (if-elseif-else) for each list/sublist.
• If original list is length 8, there are 4 sets of 2 comparisons.
• If original list is length 1024, there are 11 sets of 2 comparisons.
• The “exact” value is 2 *(log₂ n + 1)
• The order of magnitude is O(log₂ n)