D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

CHAPTER 9. NUMERIC
75
1) algorithm Factorial(n)
2)
Pre: n ≥ 0, n is the number to compute the factorial of
3)
Post: the factorial of n is computed
4)
if n < 2
5)
return 1
6)
end if
7)
f actorial ← 1
8)
for i ← 2 to n
9)
f actorial ← f actorial ∗ i
10)
end for
11)
return f actorial
12) end Factorial
9.6
Summary
In this chapter we have presented several numeric algorithms, most of which
are simply here because they were fun to design. Perhaps the message that
the reader should gain from this chapter is that algorithms can be applied to
several domains to make work in that respective domain attainable. Numeric
algorithms in particular drive some of the most advanced systems on the planet
computing such data as weather forecasts.

---

Chapter 10
Searching
10.1
Sequential Search
A simple algorithm that search for a specific item inside a list. It operates
looping on each element O(n) until a match occurs or the end is reached.
1) algorithm SequentialSearch(list, item)
2)
Pre:
list 6= ∅
3)
Post: return index of item if found, otherwise −1
4)
index ← 0
5)
while index < list.Count and list[index] 6= item
6)
index ← index + 1
7)
end while
8)
if index < list.Count and list[index] = item
9)
return index
10)
end if
11)
return −1
12) end SequentialSearch
10.2
Probability Search
Probability search is a statistical sequential searching algorithm. In addition to
searching for an item, it takes into account its frequency by swapping it with
it’s predecessor in the list. The algorithm complexity still remains at O(n) but
in a non-uniform items search the more frequent items are in the first positions,
reducing list scanning time.
Figure 10.1 shows the resulting state of a list after searching for two items,
notice how the searched items have had their search probability increased after
each search operation respectively.
76

---

CHAPTER 10. SEARCHING
77
Figure 10.1: a) Search(12), b) Search(101)
1) algorithm ProbabilitySearch(list, item)
2)
Pre:
list 6= ∅
3)
Post: a boolean indicating where the item is found or not;
in the former case swap founded item with its predecessor
4)
index ← 0
5)
while index < list.Count and list[index] 6= item
6)
index ← index + 1
7)
end while
8)
if index ≥ list.Count or list[index] 6= item
9)
return false
10)
end if
11)
if index > 0
12)
Swap(list[index], list[index − 1])
13)
end if
14)
return true
15) end ProbabilitySearch
10.3
Summary
In this chapter we have presented a few novel searching algorithms. We have
presented more efficient searching algorithms earlier on, like for instance the
logarithmic searching algorithm that AVL and BST tree’s use (defined in §3.2).
We decided not to cover a searching algorithm known as binary chop (another
name for binary search, binary chop usually refers to its array counterpart) as

---