INN701 Lecture 3
CRICOS No. 00213J
a university for the worldreal R 1
Searching algorithms
• Searching algorithms are ‘comparison-based’
– Searching is done either to confirm that a particular item exists in
a given collection, or to find a data record that is labelled with a
given search key
– The basic operation in searching is usually comparing an item in
the collection with the search key
• In this lecture, we restrict ourselves to array-based algorithms
– Pointer-based ‘search trees’ are an equally-important data
structure for searching
• There are two classical search algorithms:
– Sequential search algorithm (linear search algorithm)
– Binary search algorithm
CRICOS No. 00213J
a university for the worldreal R 2
Sequential search
• It is a brute-force algorithm
– Systematically examine each item in turn until the desired one is
found or the collection is exhausted
• It is the only algorithm possible when the collection of items is
unsorted
– In the worst case we must inspect every item
CRICOS No. 00213J
a university for the worldreal R
Sequential search
Search for 90
return 4
3
CRICOS No. 00213J
a university for the worldreal R
Sequential search
Search for 28
return -1
4
CRICOS No. 00213J
a university for the worldreal R 5
Sequential search
CRICOS No. 00213J
a university for the worldreal R
Efficiency of the sequential search algorithm
• We choose comparison A[i] ≠ K as the basic operation in this case
– We also assume that this comparison is not performed if the first
conjunct i < n is false • The worst case is when key K does not appear in array A at all, or is the last item in the array, which forces the algorithm to inspect all n items: Cworst(n) = n ∈ O(n) 6 CRICOS No. 00213J a university for the worldreal R 7 Binary search • If we know that the collection of items is sorted according to some recognised ordering criterion, we can use a decrease-and-conquer algorithm to improve searching efficiency. • A decrease-and-conquer algorithm decreases a problem instance to a smaller instance of the same problem, and then conquers the problem by solving the smaller instance of the problem. CRICOS No. 00213J a university for the worldreal R 8 Binary search • Binary search algorithm: 1. Choose the midpoint of the array 2. If the item of interest is there the search is finished 3. If the search key is smaller than the value at the midpoint, repeat the search on the lower half of the array 4. If the search key is larger than the value at the midpoint, repeat the search on the upper half of the array CRICOS No. 00213J a university for the worldreal R Binary search Search for 16 0 1 2 3 4 5 6 7 8 9 return 2 l = 0 r = 9 l = 0 r = 3 l = 2 r = 3 9 CRICOS No. 00213J a university for the worldreal R Binary search Search for 15 0 1 2 3 4 5 6 7 8 9 return -1 l = 0 r = 9 l = 0 r = 3 l = 2 r = 3 l = 2 r = 1 10 CRICOS No. 00213J a university for the worldreal R 11 Binary search • An iterative version of binary search is: CRICOS No. 00213J a university for the worldreal R 12 Efficiency of the binary search algorithm • By analysing the algorithm’s efficiency, with respect to the length n of the array and the number of comparisons between A[m] and k performed, including k = A[m] and k > A[m], we found:
2( ) log 1 (log )worstC n n O n= + ∈
Searching algorithms
Sequential search
Sequential search
Sequential search
Sequential search
Efficiency of the sequential search algorithm
Binary search
Binary search
Binary search
Binary search
Binary search
Efficiency of the binary search algorithm