Searching Algorithms
Overview
You have lost your passport somewhere in the house. One way to find it is to start in the hall and search every room in turn until you hit it. The other way, if the house is a hotel with numbered rooms and you know the number, is to walk to the middle corridor, see whether your room is above or below, and ignore half the building. Both plans find the passport. Only one of them is any use in a hotel with a thousand rooms.
Those two plans are the linear search and the binary search, and this specification wants three things from you: the mechanics of each, the ability to follow and write pseudocode for both, and a clear-eyed comparison of where each one wins. The comparison is not simply that binary is faster. Binary search demands something in return, and knowing what it demands is the difference between a two-mark answer and a four-mark one.
Objectives
- Understand and explain how the linear search algorithm works.
- Understand and explain how the binary search algorithm works.
- Compare and contrast linear and binary search algorithms.
Mind map
This topic is mapped out so you can see how the ideas connect.
Open the mind map in the app
Lesson Note
Complete Note Available on the Green Bridge App
Get the Green Bridge CBT app on your phone or computer for the complete IGCSE library: past papers, mark schemes, mind maps, flashcards and audio lessons.
Lesson Evaluation
Congratulations on completing the lesson on Searching Algorithms. Now that youve explored the key concepts and ideas, its time to put your knowledge to the test. This section offers a variety of practice questions designed to reinforce your understanding and help you gauge your grasp of the material.
You will encounter a mix of question types, including multiple-choice questions, short answer questions, and essay questions. Each question is thoughtfully crafted to assess different aspects of your knowledge and critical thinking skills.
Use this evaluation section as an opportunity to reinforce your understanding of the topic and to identify any areas where you may need additional study. Don't be discouraged by any challenges you encounter; instead, view them as opportunities for growth and improvement.
- Which condition must be met before a binary search can be used? A. The data must be stored in a file B. The data must be numeric C. The data must be sorted D. The data must contain no duplicates Answer: C
- An array holds 64 sorted items. What is the maximum number of comparisons a binary search will make? A. 6 B. 8 C. 32 D. 64 Answer: A
- A linear search is used on an array of 40 items to look for a value that is not present. How many comparisons are made? A. 1 B. 20 C. 39 D. 40 Answer: D
- In an iterative binary search, which assignment is made when the middle element is smaller than the target? A. First becomes Middle B. First becomes Middle + 1 C. Last becomes Middle D. Last becomes Middle - 1 Answer: B
- Which of the following is an advantage of a linear search over a binary search? A. It makes fewer comparisons on large data sets B. It works on data that is not in any order C. It halves the search area at each step D. It can only be used on arrays Answer: B
Work through these questions in the app
Work through these questions in the app
Recommended Books
Practice Mock Questions
Want to practice mock questions on Searching Algorithms? Download the Green Bridge CBT app to access mock questions and full practice assessments for this topic.
Download The App On Google Playstore
Everything you need to excel in your exams
