Searching Algorithms

binary-and-linear-search-animations

You need to have an understanding of the following:

  • Linear Search (Sequential)
  • Binary Search

aHR0cDovL21lZGlhLmJlc3RvZm1pY3JvLmNvbS9MLzkvNTEzOTgxL29yaWdpbmFsL2lvc185X25vdGVzX2ljb24uanBn

Your notes should include the following (use revision guide page 36 to help)…

BINARY SEARCH

-What type of list is needed to perform a binary search?

-The four steps of a binary search

-Advantages of a binary search

LINEAR SEARCH

-The Four Steps of a Linear Search

-Whats good about a Linear Search?

-Whats bad about a Linear Search?

SEARCHING TASKS

First, have a go at the following exam question in your exercise book.

Binary Search

Click for Marking Scheme

Second, have a go at this linear search Python task…

 

 

 

Can you now code a Linear Search in Python? Create a program for a travel company. The program should allow the user to INPUT a destination and then use a linear search to identify whether this is a destination that the company flies to. The program should then OUTPUT an appropriate message. Look at the example below and then have a go yourself…

NOTE: Use a list to store the travel destinations

Picture1

Extension: Can you edit your program so that it outputs “Sorry, this is not a destination that we offer” when the input is not in the list.

Picture1

Click for Help!

Finally, have a go at the Knowledge Check

LINEAR SEARCH

BINARY SEARCH

Watch the following video until 2:25 for an excellent explanation of a Binary Search…