Searching Algorithms

Click to see the rest of the Algorithms section :

Searching Algorithms, like sorting can range from very simple to complex. One thing that you will need to be aware of when selecting a searching algorithm is whether the data that you are searching is already sorted.

Binary Search - GCSE Computer Science

Imagine that you have been asked to find a particular book on a bookshelf 10m long (long shelf!). What method would you choose to locate the book in the shortest time possible?

You could start at the beginning and check each book in turn until you found the book that you were looking for…

This is a legitimate algorithm that will eventually help you find your book. This is known as Linear Search and is used when we have a small number of items to search through and the items in our list are not sorted. In pseudocode, the algorithm would look like:

i<-- 0

Book <-- "Teach All About IT - The Definitive Guide"

WHILE (myShelf[i] <> Book) AND (myShelf[i] < LENGTH(myShelf)) DO

    i <-- i+1

 

But what if the books on the shelf were in order? With a 10 meter bookshelf, surely there is a better way to search for the book that we want? There is – it’s called Binary Search

Binary Search is also known as Divide & Conquer because every time we try an option, if we follow the rules of the algorithm the list is reduced by half. In this way, a list of 100 items can be sorted through in just 7 steps!

In order to use Binary Search, we must start with a sorted list and select the middle item (if the list has an even number of items, then middle – 1).

We then pose the question “Is the book higher than this book?”

IF yes, then it’s in the top half of the shelf, otherwise it’s in the bottom half.

Try this for yourself by guessing a random number between 1 & 100 using the following algorithm:

Found <- False

Bottom <-- 1

Top <-- 100

WHILE Found <- False

   Mid <-- (Bottom + Top)/2

   IF myList[Mid] > Search THEN

          Top <-- Mid-1

   ELSE IF myList[Mid] < Search THEN

          Bottom <-- Mid +1

   ELSE

          Found <-- True

   END IF

END WHILE

Find this page helpful? Share the love on your social media mentioning @TeachAllAboutIT and we’ll enter you in our monthly draw to win a gift voucher for any product on the site!

Share on facebook
Share on google
Share on twitter
Share on linkedin
Share on pinterest
Share on reddit

More For Members

Lesson Plan

Coming Soon!

Presentation

Coming Soon!

Homework

Click to download

Students

Click to revise!

Not a member yet? Sign Up Here

Sign Up For Membership Today

Computer Science Student

Individual Site License
Topic Introduction Pages
Additional Revision Resources
Revision Videos
Exam Question Walkthroughs
Discounted Group Lessons
£2.50 per Month. After your initial payment, your first payment is Free.

Whole School

Whole School Site License (teacher access)
Up to 50 student accounts (£3 per student, per annum for additional students)
Online Topic Lesson Plans
Differentiated Homework Tasks
Monthly Bundle of Downloadable Resources
Discounted Live Lessons
£12.50 per Month.
Number of courses 00
GET IT NOW GET IT NOW