Searching algorithms
Lesson support: Support for your students
Make sure you have looked through this previous entry in this series first to understand the importance of algorithms.
Prerequisites:
- Know what an algorithm is
- Be able to read Pseudocode
Definitions
Algorithm: A process or set of rules to be followed.
Array: A data structure that holds multiple items (Integers or Strings for example).
Binary Search: An algorithm to look for a target within an array, by deciding for a pivot if the element is in the first or second half of the array.
Comparison: The act of comparing two things.
Divide and conquer: An algorithm that works by breaking a problem down into one or two sub-problems, repeatedly, until the problem is so small that it can be solved.
Integer: Simply put, a whole number.
Linear Search: An algorithm to look for a target within an array, starting with the first item and moving through the next one in turn until the element is found.
Searching: The process of looking for something in a set of those things.
String: An ordered sequence of characters, can be thought of as a word or sentence.
Zero-indexed: A way of numbering starting at zero (0) rather than 1.
Searching Arrays
To find an item on a computer, we need to think like a computer. Each time a computer checks to see if the item is the one it wants, that is a comparison.
And here is the thing: Comparisons cost time.
Now computers are inherently ordered things. If you have a large collection of numbers (and let us use numbers as examples of searching) you would put them together in an array.
An array to store elements
An array is simply a collection of something.
We are going to use a numbers collection (known as an Integer array in computing).
You’ll notice that the first element in the array (15) is at position 0. This is not an accident, as this is a zero-indexed array. The element at position 3 is 112, the 4th element in the array.
Arrays can store other things, like characters or words but for this section regarding searching we are going to restrict our work to Integer (number) arrays)
The search
In this case we are going to look for the number 104 in an array containing the elements 15, 2, 104, 112 and 3.
target = 104
We are going to look at the strategies of an impossible search, random search, linear search and binary search for finding our element.
The impossible search: looking for everything at once
As humans you might think that you can find something by simply looking at everything at once in the array. Unfortunately, computers can only do one thing at once. More precisely, the computer can only look in one location in the array at any time.
For example we can investigate the first element of the array for the target 104.
This is a comparison. We compare the first element of the array (at position 0) with the target 104, and the result is false. That is 104 is not at the first element in the array.
We can now think about the best way to find an element in the array.
The random search
We can randomly pick a number from 0 to 4 (that is, some element of the array between the first and the fifth in this case) and see if it is the target.
The problem comes in that we might pick one element more than once, meaning that by chance we could keep picking the first element — for ever! We would need to keep a record of which elements we have investigated, and this becomes more complex and no better than performing a more logical linear search.
The linear search
The linear search looks through all elements of the array one at a time. Remember we are looking for 104.
We can improve this. Once we have found our element (104) we can stop, as there is no reason if we looking for 104 to keep looking after we have found it!
Here is the algorithm in pseudocode form:
Here is the algorithm in flowchart form:
No linear search is fine for small arrays. But you might have to compare every element in the list so for longer lists this can be many, many comparisons. There has to be a better way!
The binary search
If you have a large array to search through, you can use a binary search. A good example of this is searching through a large set of contacts on your mobile phone (but makes even more sense if you had a million friends!).
The binary search has a condition. Your array needs to be ordered. We will assume that your input array is in numerical order.
Here is our new, ordered array:
And we have a new target, 8
target = 8
Now how do we find out which half of the list that the target exists in? We choose a pivot and see if the target is on the left or right of that element.
The algorithm:
Try 1
Choose a pivot (here we will choose the middle)
The target we are looking for is not the pivot (4 != 8)
The target is on the right-hand side of the array (since 8 > 4)
Try 2
Choose a pivot on the right hand side of array (here we will choose the middle).
The target we are looking for is the pivot (8= 8) so we are done!
The algorithm in words:
1.Choose a pivot (let us go for the middle)
2. Is the target we are looking for is not the pivot
3.Try to find the target on one side of the list:
If target < pivot perform 1–3 on the left hand side of the list
else perform 1–3 on the right hand side of the list
Here is the algorithm in pseudocode form:
Here is the algorithm in flowchart form:
Comparing the methods
For a start, let us throw out the random method. It might never find the target, and should not be used (even if you feel particularly lucky).
The linear search for an array of n elements. You might get lucky and the target is the first element you look at. But you may have to look at every possible element we may have to perform n comparisons. The worst case is n comparisons.
The binary search halves and halves again. Once again you might get lucky and the target is the first element you look at. Mathematicians and those interested in this stuff will be familiar with this half and half again relationship. The worst case is log n to find the element.
Rounding up
It can be tricky thinking about this the first time, no doubt about it. However practicing and moving through trace tables will help. Coding will also help!
Teaching this to a class? Use the accompanying lesson plan and worksheets on tes, exclusively from StudeApps.