In deze les zitten 17 slides, met tekstslides en 2 videos.
Lesduur is: 60 min
Onderdelen in deze les
year 10 searching algorithms
Slide 1 - Tekstslide
year 10 searching algorithms
Do now..
Name a sorting algorithm.
Describe what it does.
Slide 2 - Tekstslide
By the end of this lesson you will know what searching and sorting algorithms are.
Slide 3 - Tekstslide
There are two searching algorithms binary and linear.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Slide 4 - Tekstslide
A binary search only works on a ordered list and uses a n+1/2 approach to searching, this means finding the middle term, is this what we are looking? if not is our item in the left or right side of the middle?
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Slide 5 - Tekstslide
Slide 6 - Video
step 1 - find the middle
step 2 - is this what we are looking for?
step 3 - is our item lower or higher?
step 4 - remove the side of the list we dont need
step 5 - repeat steps 1-4 on the new list until we find our item.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Slide 7 - Tekstslide
Example... Find 99
Find the middle 9+1/2 = 5 so the 5th position, 68
is 99 higher or lower than 68?
It is higher so delete the lower half of the list.
Find the middle 4+1/2 = 2.5 we then round up so 3rd position, 99.
We have found our number.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
7
21
52
59
68
92
94
99
133
92
94
99
133
Slide 8 - Tekstslide
Your turn... Find 22
In your books describe the steps a binary search would use to find 22
LO - By the end of this lesson you will know what searching and sorting algorithms are.
10
12
22
33
44
55
66
Slide 9 - Tekstslide
Answer... Find 22
middle 7 + 1 /2 = 4, 4th is 33,
22 is lower so del the higher half (right)
middle is 3 + 1 /2 = 2, 2nd position is 12
22 is higher so delete the lower half (left)
LO - By the end of this lesson you will know what searching and sorting algorithms are.
10
12
22
33
44
55
66
10
12
22
22
Slide 10 - Tekstslide
Linear search
Check each number to see if it what we want this does not need to be sorted list just go through each position one by one.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
21
7
59
52
92
68
99
94
133
Slide 11 - Tekstslide
Slide 12 - Video
Linear search
Find 99 again.
check the first number 21 is this 99, no continue.
check the second number 7 is this 99 no continue.
Repeat until you find 99.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
21
7
59
52
92
68
99
94
133
Slide 13 - Tekstslide
Your turn Linear search
in your books describe the steps that a linear search would take to find Huw.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Rob
Anna
Huw
Emma
Patrice
Iqbal
Slide 14 - Tekstslide
Linear code snippet
# Linear Search Function
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # return the index where found
return -1 # not found
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Slide 15 - Tekstslide
Binary code snippet
# Binary Search Function (requires sorted list)
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # not found
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Slide 16 - Tekstslide
Summary:
Linear search → simpler, works on any list, but slower.
Binary search → faster, but requires a sorted list.
LO - By the end of this lesson you will know what searching and sorting algorithms are.
Lesduur is: 60 min
