2.
1 ALGORITHMS L8 Searching Algorithms
STARTER
Find Wally!
How did you do it?
What was your process?
SEARCHING
How do you search for an item that Linear search – Each item in the
you have lost? Or search for a book list is checked in order from the
in a library? start of the list until the item is
found.
How does a search engine find
specific websites? Binary search – An ordered list
(i.e. smallest to largest) is split into
How would you tell a computer two each time a comparison is
how to search for something? made
LINEAR SEARCH
A linear search allows us to search for values even if
the values are not in order.
Linear search:
−Check the first value
−IF it is the value you are looking for
o Celebrate and stop
−ELSE move to the next value and check
−REPEAT UNTIL you have
checked all the elements
and not found the value
you are looking for
EXAMPLE
Value
Number
Search the list to see if 102 is in it.
Get the first value
Is it 102?
No, move to get the next value (the second)
Is it 102? No
EXAMPLE
No, move to get the next value (third)
Is it 102?
No, move to the next element (4th)
Is it 102?
No, move to the next element (5th)
Is it 102?
Yes – celebrate and stop
ALGORITHM
Try and write an algorithm for item = item to find
the linear search.
list = [items in list]
for value in list
IF value==item
PRINT “Value
found”
ENDIF
ENDFOR
WHITEBOARD CHECK
How many searches to find the number 22?
Consistently finding the
middle
When you have a number like 9
BINARY SEARCH and you want to find the midway
point, if you divide by 2 then we
get 4.5 so do we round up or
down?
The list needs to be in order for a binary search
When you have a number like 8
Take the middle value. and you want to find the midway
point, how does this work
Compare to the value you are looking for. because there is an even amount
of numbers?
IF it is the value you are looking for.
Celebrate, and stop. Use this algorithm every time to
get consistent results!
ELSEIF it is larger than the one you are looking for.
Take the list to the left of the middle value.
Lowest position + highest
ELSEIF it is smaller than the one you are looking for.
position // 2
Take the list to the right of the middle value.
REPEAT with the new list Let’s see how this works…
BINARY SEARCH –
SEARCHING FOR 9
Value
Number
Take the middle value – lowest position + highest position DIV 2 (1+10=11 // 2 = 5)
Is this equal to, greater than, or less than 9?
16 > 9 so make a new list with all the numbers to the left
BINARY SEARCH –
SEARCHING FOR 9
Search the new list for 9
Take the middle value - lowest position + highest position DIV 2 (1+4=5 // 2 = 2)
Is this equal to, greater than, or less than 9?
Smaller than, so take the numbers to the right
BINARY SEARCH –
SEARCHING FOR 9
Search the new list for 9
Take the middle value - lowest position + highest position DIV 2 (3+4=7 // 2 = 3)
Is this equal to, greater than, or less than than 9?
Equal to! Celebrate, and stop you’ve found it.
BINARY SEARCH WITH 0 DON’T PANIC!!!
INDEX
Value 0 1 2 3 4 5 6 7 8 9
Number 2 6 9 12 16 18 20 23 45 99
The algorithm is exactly the same!
Find middle – highest value + lowest value DIV 2.
0 + 9 = 9 // 2 = 4
Too big, disregard the right side of the list
0 + 3 = 3 // 2 = 1
Too small, disregard the left side of the list
2 + 3 = 5 // 2 = 2
YAY!
ALGORITHM
Try and write the algorithm for a val = item to find
binary search arr = [items in list]
left = 1
right = LENGTH(arr)
WHILE left != right
mid = (left + right) DIV 2
IF val ≤ arr[mid] THEN
right = mid
ELSE
left = mid + 1
ENDIF
ENDWHILE
WHITEBOARD CHECK
How many searches to find the number 22?
WHITEBOARD CHECK
How many searches to find the number 99?
ALGORITHM COMPARISON
Linear Binary
item item to find val ← item to find
arr ← [items in list]
list [items in list] left ← 1
right ← LENGTH(arr)
for value in list WHILE left != right
IF value==item mid ← (left + right) DIV 2
IF val ≤ arr[mid] THEN
PRINT “Value found” right ← mid
ELSE
ENDIF left ← mid + 1
ENDFOR ENDIF
ENDWHILE
OneNote - 2.1 L8 Searching
Algorithms
SEARCHING ALGORITHMS
Any questions?
Complete your searching algorithm tasks.
OneNote - 2.1 Ext: L8 Searching
Algorithms
EXTENSION
Task 1:
Go to the extension on your OneNote 2.1 Ext: L8 Searching
Algorithms
