2.1.3a Searching and Sorting Algorithms (Linear and Binary Search Algorithms) - OCR GCSE.pptx
Linear & Binary Search Algorithms
www.computerscienceuk.com
Lesduur is: 75 minOnderdelen in deze les
Linear & Binary Search Algorithms
www.computerscienceuk.com
Starter Activity
3 minutes
If you were given a set of data and asked to find a particular value within the dataset, what would you do?
Learning Habits
Collaboration:
Working effectively with others
Listening…
…to understand
Empathising…
…with feelings and views
Imitation:
Picking up good habits from others
Independence:
Working effectively alone
Questioning:
Asking questions to get below the surface
Imagining…
…how things could be and seeing a range of possibilities
Reasoning:
Thinking rigorously, methodically and giving explanations.
Capitalising:
Using resources purposefully
Managing distractions…
…and sustaining concentration
Effective use of time
Noticing details
Perseverance:
Overcoming frustration and difficulty
Planning…
…your learning in advance
Adapting :
Reflecting and making changes
Meta Learning:
Talking about how you have been learning
Distilling…
…what you have learnt and what you need to learn
Which ‘Learning Habits’ we will need to make use of to be a success in this lesson?
Lesson Objectives
Lesson Objectives
To understand how the linear search algorithm works.
To understand how the binary search algorithm works.
Success Criteria
ALL: To be able to describe the steps taken to perform both a linear search and a binary search.
MOST: To also be able to compare the algorithms’ relative efficiencies.
SOME: To also be able to write both the linear search and binary search algorithms.
Searching Algorithms
Search algorithms are used to find items of data.
There are some standard algorithms that have been developed and each have their own merits.
Over the next few slides we will take a look at two common search algorithms:
Linear Search Algorithm
Binary Search Algorithm
Linear and Binary Search Algorithms
Linear Search
Linear searching simply involves searching through a set of data, one item after the other, until the item we are looking for is found.
Lets take a look at an example of using a linear search algorithm to find an item of data in an array.
Imagine we are searching for the letter ‘D’.
A linear search algorithm will be set up to cycle through each index of the array.
IF it finds a ‘D’, it knows to stop and display the location.
ELSE it will add 1 to the index (move to the next item) and look there.
Linear and Binary Search Algorithms
Linear Search
The Algorithm presented
as a flowchart:
Linear and Binary Search Algorithms
position = 0
found = False
WHILE (position < length(array)) AND (found == False):
IF search_item == array[counter]
DISPLAY “Item at position” counter+1
found = True
ELSE:
position = position + 1
Linear Search
The Algorithm presented
as pseudocode:
Linear and Binary Search Algorithms
Binary Search – DIVIDE AND CONQUER
Binary searching is only possible for sets of data that are in ORDER – THEY HAVE TO BE ORDERED!!
It involves starting the search at the middle to work out if the search item is positioned lower than the middle or higher than the middle.
If it is positioned lower than the middle, the search is narrowed to the first half of the data set.
If it is positioned higher than the middle, the search is narrowed to the second half of the data set.
Once the data set is halved, the search then continues as it did before, in the middle.
By continually dividing the data set until the item is found, the time taken to search for an item can be much faster than using a linear search.
Linear and Binary Search Algorithms
Binary Search – DIVIDE AND CONQUER
Lets say that we are searching for the letter ‘G.
We would begin by looking at the middle item.
To do this we would identify the lower bound and the upper bound of the data set.
Then we would add the ‘lower bound’ to the ‘upper bound’ and divide by 2, in order to find the position of the middle item (mid-point): (10-0)/2 = Midpoint = 5
The item at position 5 is the letter “F”.
“F” is lower than the letter “G”.
We now narrow our data set by focusing on the second half of the set.
LB
UB
Linear and Binary Search Algorithms
Binary Search – DIVIDE AND CONQUER
The lower-bound moves to the position one up from the mid-point…
…and we repeat the same process again.
We add the ‘lower bound’ to the ‘upper bound’ and divide by 2, in order to find the position of the middle item (mid-point): (10+6)/2 = Midpoint = 8
The item at position 8 is the letter “I”.
“I” is higher than the letter “G”.
We now narrow our data set by focusing on the first half of this new, smaller set.
LB
UB
Linear and Binary Search Algorithms
Binary Search – DIVIDE AND CONQUER
The lower-bound moves to the position one down from the mid-point…
…and we repeat the same process again.
We add the ‘lower bound’ to the ‘upper bound’ and divide by 2, in order to find the position of the middle item (mid-point): (7+6)/2 = Midpoint = 6.5
ISSUE! WE DON’T HAVE AN INDEX 6.5!
OK, what we do is round the answer up to 7 and use this as our midpoint.
The item at position 7 is the letter “H”.
“H” is higher than the letter “G”.
We now narrow our data set by focusing on the first half of this new, smaller set.
LB
UB
Linear and Binary Search Algorithms
Binary Search – DIVIDE AND CONQUER
The lower-bound moves to the position one down from the mid-point…
…and we repeat the same process again.
We add the ‘lower bound’ to the ‘upper bound’ and divide by 2, in order to find the position of the middle item (mid-point): (6+6)/2 = Midpoint = 6
The item at position 6 is the letter “G”.
SUCCESS!!
We have now found them item we were searching for!!
LB
UB
Linear and Binary Search Algorithms
Binary Search
The Algorithm presented
as a flowchart:
Linear and Binary Search Algorithms
found = False
first = 0
last = lengthOfList – 1
WHILE found = False:
midPoint = (first + last) DIV 2
IF list[midpoint] == itemSought:
PRINT “item found at location”, midpoint
found = True
BREAK
ELSE:
IF first >= last:
PRINT “Failed”
BREAK
ELSE:
IF list[midpoint] > itemSought:
last = midpoint - 1
ELSE:
first = midpoint + 1
Binary Search
The Algorithm presented
as pseudocode:
Linear and Binary Search Algorithms
Search Algorithms – A Quick Comparison
