Searching algorithms

Quick links

3.1

Fundamentals of algorithms

3.1.1

Representing algorithms

3.1.2

Efficiency of algorithms

3.1.3

Searching algorithms

3.1.4

Sorting algorithms

Syllabus content

Content   Additional Information
Understand and explain how the linear search algorithm works.   Students should know the mechanics of the algorithm.
     
Understand and explain how the binary search algorithm works.   Students should know the mechanics of the algorithm.
     
Compare and contrast linear and binary search algorithms.   Students should know the advantages and disadvantages of both algorithms.

 

Linear Search

Demonstration by example.

If there is a list of values and a search criterion what would be the algorithm that would find the position of the search criterion in the given list? This is a 10 item list called for argument's sake List[] and we are searching for a value S in the list List[]. (In Python List[] will be an array variable indicated by the square brackets.)

6 4 9 23 16 30 24 5 8 2

 

For the purposes of the trace table S will have the value 30.

"In Linear Search the list List[] is searched sequentially and the position is returned if the value S to be searched is available in the list, otherwise -1 is returned. The search in Linear Search starts at the beginning of an array and move to the end, testing for a match at each item."

Here is the pseudocode for the linear search, however, all the lines of code are here but not necessarily in the right order. In Word arrange these lines of code in the right order to see if you get a working algorithm. Use the text above to help and remember that the program will have to receive user input at the start so it knows what the list is and what the search criterion is.

For Index in List
S <- user input
Result <- Index
Result <- -1
End if
If List[Index] = S
Index <- 0
Index <- Index + 1
List[] <- user input
End for

Use a trace table to see if you are right. Copy and complete the table in Word. As there are ten items in List[] there will be ten iterations.

Iteration

List[Index]

Result

Index

1

 

 

 

2

 

 

 

3

 

 

 

4

 

 

 

5

 

 

 

6

 

 

 

7

 

 

 

8

 

 

 

9

 

 

 

10

 

 

 

 

Draw the flowchart for this algorithm.

Do you see how the FOR loop has been treated? the effective (decision) part of the loop is at the end "Have we reached the last item in the list?" If not the routine is repeated.

Is there a way of making this linear search more efficient? Hint: the list is altered in some way and the algorithm chamged slightly to accommodate the change.

Adapt the algorithm to include this efficiency. On average it should halve the time taken to find the value S in the list List[].

Draw the flowchart for this improved algorithm.

Would using a While loop (a condition controlled loop) be a better solution than a For loop (an iteration controlled loop)?

How would this affect the algorithm?

Write the new algorith that incorporates the While loop and then draw the flowchart.

  1. Add a counter to report how many searches have been done for each item searched for.
  2. Add the functionality to add an item to the list if it is not found.

Extension Activity

Making the search algorithm just that little bit more difficult.

  1. Add a counter to report how many searches have been done for each item searched for.
  2. Add the functionality to add an item to the list if it is not found in the List[].

Binary Search

A binary search only works on data that is sorted.

If there is a list of values and a search criterion what would be the algorithm that would find the position of the search criterion in the given list? This is a 10 item, ordered list called for argument's sake Ordered_List[] and we are searching for a value S in the list Ordered_List[].

2 4 5 6 8 9 16 23 24 30

 

For the purposes of the trace table S will have the value 16.

A binary search involves the concept of Recursion. This is a very powerful computational technique that allows the same piece of code to be called by itself to performa another task on the data.

So I will use the Binary Search as an example. I start by dividing the Ordered_List[] in two. If the value is somwhere in the list it must now be in only one half of the Ordered_List[]. As the list is ordered I can test to see which half the Ordered_List[] the value S is in. If I am searching for S (being 16) then I divide the list at the 5th item and as S (16) is greater then Ordered_List[4] (because Ordered_List[4] is 8 - remember we start counting from 0 in computing) the value S must be in the second half of the list. I then repeat the process on the second half of the list.

For all intents and purposes the list is now only 5 items long.

9 16 23 24 30

 

I repeat the process, dividing the Ordered_List[] in two again (this time at item 1 - 16) as you should round down to be consistent) This time the value S is in the lower half of the list so the upper half is dicarded leaving the list at two items.

9 16

 

Finally the Ordered_List[] is split in two and the value is found in the upper half which is a single value. Therefore S exists in the Ordered_List[].

Here is the pseudocode for the boinary search, however, it involves a function. A function is a section of code that has a name and will return a value. In this case the function is called BinarySearch()

Function BinarySearch (List[], Value, start, end)
If start > end  Return -1
Middle = int(Len(list[]/2))
Value = List[Middle]
If value < List[Middle] then BinarySearch (List[], Value, start, middle -1)
If value > List[Middle] then BinarySearch (List[], Value, middle +1, end)

The function is called with the code

BinarySearch (List[], S, 0, Len(List[]-1))

See if you can draw the flowchart for this algorithm. It is much more difficult and you may need more than one attempt to get it right.

What is the limitation with the binary search?

Why is there a -1 in the function when it is called?

3.1 Fundamentals of algorithms

3.2 Programming

3.3 Fundamentals of data representation

3.4 Computer systems

3.5 Fundamentals of computer networks

3.6 Fundamentals of cyber security

3.7 Ethical, legal and environmental impacts of digital technology on wider society, including issues of privacy

3.8 Aspects of software development

Glossary and other links

Glossary of computing terms.

AQA 8520: The 2016 syllabus