Departments› Computer Science› Module V› Algorithms And Data Structures› Ch 5: Search Techniques
Computer Science  ·  Level 6
Algorithms And Data Structures
Chapter 5: Search Techniques
📚 4 Topics
← Chapters ⬇ Download PDF
⚑ What you will be able to do

By the end of this chapter, you will be able to:

  • perform search operations effectively to find the data you need.
  • carry out linear search accurately to locate specific elements.
  • execute binary search correctly on sorted data sets.
  • choose and apply different search techniques appropriately to solve various problems.

Mastering these search skills will help you work smarter and faster in any tech-related task or project.

5.1 Definition of search

Searching is the process of finding whether a particular value, called the key or target, is present in a collection of data, and if so, where it is located. A search algorithm is the step-by-step procedure used to do this. Searching is one of the most common operations in computing: every login, database lookup, spell check and phone contact search depends on it, so the choice of search algorithm strongly affects how fast a program runs.

Example: an M-Pesa agent in Ugunja who looks up a customer's transaction by its reference code is performing a search; the agent's software must find one record among thousands in a fraction of a second.

Key terms

  • Search key (target): the value being looked for, such as an ID number or name.
  • Search space: the collection being searched, such as an array, list, tree or table.
  • Successful search: the key is found and its position (index) is returned.
  • Unsuccessful search: the key is not present; the algorithm returns a signal such as -1.
  • Comparison: checking whether an element equals, is less than or greater than the key; the number of comparisons measures efficiency.

Classification of search algorithms

  • Sequential (linear) search: examines elements one after another; works on unsorted data.
  • Interval search: repeatedly divides a sorted search space, for example binary search, jump search and interpolation search.
  • Hash-based search: computes the position of the key directly with a hash function, giving average constant time.
  • Tree search: follows a path in a binary search tree, B-tree or similar structure.
  • Graph search: explores connected nodes, for example breadth-first and depth-first search.

Internal and external searching

  • Internal search: all data is in main memory, for example an array in a program.
  • External search: data is on disk, as in database files; algorithms try to minimise disk reads, often with B-tree indexes.

Measuring search efficiency

Efficiency is expressed with Big-O notation, which describes how the number of comparisons grows with the number of elements n.

Algorithm Best case Average case Worst case Requires sorted data
Linear search O(1) O(n) O(n) No
Binary search O(1) O(log n) O(log n) Yes
Hash table lookup O(1) O(1) O(n) No

Factors in choosing a search technique

  • Size of the data set: small lists can be searched linearly; large ones need faster methods.
  • Whether data is sorted: binary search needs sorted data.
  • Frequency of searches compared with updates: frequent searches justify the cost of sorting or indexing.
  • Data structure: arrays allow direct indexing; linked lists allow only sequential access.
  • Memory available: hash tables and indexes use extra memory.
The rest of this chapter
🔒

Create a free account to open more of this chapter.

Free: practical guides, quick cards, workplace scenarios and more.

Create a free account
🔒5.2 Explanation of Linear Search

Linear search, also called sequential search, checks each element of a list in order, starting from the first, until it finds the key or reaches the end. It is the simplest search algorithm and works on any list, sorted or unsorted, and on structures such as l…

🔒5.3 Explanation of Binary Search

Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it. Each comparison halves the search space, so even very large lists are searched with few comparisons. It is an example…

🔒5.4 Demonstration of linear search and binary search using C++

This topic implements linear and binary search in C++, tests them on sample data and compares their performance. The programs use std::vector, follow the algorithms in 5.2 and 5.3, and also show the binary search functions provided by the C++ Standard Library.…

Chapter Practical Activities

Practical 1: Define and Illustrate Search in Algorithms

Computer Science · Level 6
Algorithms And Data Structures
PRACTICAL ASSESSMENT
TIME: 4 HOURS
⬇ PDFCandidate Instructions (Candidate Tool)

Type: Individual

INSTRUCTIONS TO CANDIDATE:
1.  You are required to perform the following task:
i.  Write a C++ program snippet demonstrating linear search on an array of 10 integers and provide a clear, concise definition of search in algorithms on two plain papers.
2.  You have been provided with the following resources for the practical task:
Tools & EquipmentMaterials
Working computerTwo plain papers
C++ IDE
⬇ PDFResources Required (Cutting List)
S/NItemQuantity
1Working computer1 Pc per Candidate
2C++ IDE1 Pc per Candidate
3Two plain papers2 Pcs per Candidate
⬇ PDFAssessor Guide
Items to be EvaluatedMarks AvailableMarks ObtainedComments
TASK 1: Define Search in Algorithms
Observed computer laboratory rules
(Award 2 marks for compliance, or zero)		2
Wrote a clear and correct definition of search in algorithms on paper
(Award 5 marks for a complete and accurate definition, or zero)		5
Sub-Total7
TASK 2: Write Code Snippet for Linear Search
Launched C++ IDE correctly
(Award 2 marks for successful launch, or zero)		2
Declared and initialized an integer array of size 10
(Award 2 marks for correct declaration and initialization, or zero)		2
Implemented linear search function with correct parameters
(Award 5 marks for correct function implementation, or zero)		5
Correctly searched for a target integer value in the array
(Award 4 marks for correct search logic, or zero)		4
Displayed appropriate message if element found or not found
(Award 3 marks for correct messaging, or zero)		3
Compiled, debugged, and executed program successfully
(Award 3 marks for successful execution, or zero)		3
Sub-Total19
PRODUCT CHECKLIST
Definition of search is clear, concise, and accurate
(Award 5 marks for an accurate and well-written definition, or zero)		5
Code snippet compiles and runs correctly, performing linear search as specified
(Award 10 marks for a working, correct program, or zero)		10
Sub-Total15
GRAND TOTAL41
ASSESSMENT OUTCOME:   ☐ Competent    ☐ Not Yet Competent (competent if at least 50%)

Practical 2: Implement and Test Linear Search Algorithm in C++

Computer Science · Level 6
Algorithms And Data Structures
PRACTICAL ASSESSMENT
TIME: 4 HOURS
⬇ PDFCandidate Instructions (Candidate Tool)

Type: Individual

INSTRUCTIONS TO CANDIDATE:
1.  You are required to perform the following task:
i.  Write and test a C++ program that performs linear search on an integer array of size 10 and outputs the index of the target element if found or an appropriate message if not found.
2.  You have been provided with the following resources for the practical task:
Tools & EquipmentMaterials
Working computerPlain paper
C++ Integrated Development Environment (IDE)
⬇ PDFResources Required (Cutting List)
S/NItemQuantity
1Working computer1 Pc per Candidate
2C++ Integrated Development Environment (IDE)1 Pc per Candidate
3Plain paper2 Pcs per Candidate
⬇ PDFAssessor Guide
Items to be EvaluatedMarks AvailableMarks ObtainedComments
TASK 1: Implement Linear Search Program
Observed computer laboratory rules
(Award 2 marks for observing rules or zero)		2
Launched the C++ IDE correctly
(Award 1 mark for successful launch or zero)		1
Declared and initialized an integer array of size 10
(Award 2 marks for correct declaration and initialization or zero)		2
Implemented a function for linear search with appropriate parameters
(Award 2 marks for function name, 3 marks for correct parameter use and return type or zero)		5
Used a loop to iterate through the array elements correctly
(Award 3 marks for correct loop structure or zero)		3
Compared each element with the target value within the loop
(Award 2 marks for correct comparison or zero)		2
Returned the index of the found element or -1 if not found
(Award 3 marks for correct return logic or zero)		3
Displayed appropriate messages for element found or not found
(Award 3 marks for correct and clear console output or zero)		3
Commented the code adequately explaining key sections
(Award 1 mark for each relevant comment, max 2 marks)		2
Compiled, debugged, and executed the program successfully
(Award 2 marks for successful execution or zero)		2
Sub-Total25
PRODUCT CHECKLIST
Program correctly finds and returns index of target element in array of 10 integers
(Award 10 marks for correct functionality matching requirements or zero)		10
Sub-Total10
GRAND TOTAL35
ASSESSMENT OUTCOME:   ☐ Competent    ☐ Not Yet Competent (competent if at least 50%)
🔒

Free: practical guides, quick cards, workplace scenarios and more.

Create a free account
🔒Implement Binary Search Algorithm in C++Practical 3
🔒Develop a C++ program demonstrating linear searchPractical 4
🔒Develop a C++ Program Demonstrating Binary SearchPractical 5
🔒Development and Performance Analysis of Linear and Binary Search Algorithms in C++Practical 6
🔒Flowchart Creation for Linear and Binary Search AlgorithmsPractical 7
🔒Modify Linear Search Program to Find All Occurrences in C++Practical 8
🔒Implementation of Recursive Binary Search in C++Practical 9
🔒Validate Linear and Binary Search Algorithms in C++Practical 10
Flashcards 20 cards Study deck ▾
Question
1

↻ Tap card to reveal answer
🔒

18 more in this section.

Create a free account
Test Yourself 17 questions Start quiz ▾
0%
0 / 2
🔒

15 more in this section.

Create a free account
Am I competent?

At the start of this chapter we promised you would be able to:

  • perform search operations effectively to find the data you need.
  • carry out linear search accurately to locate specific elements.
  • execute binary search correctly on sorted data sets.
  • choose and apply different search techniques appropriately to solve various problems.

Tick each one you can genuinely do.

So, are you there yet?

You're competent when you can confidently do 50% or more of what this chapter promised.

Sign in to record how you're doing.

← Ch 4: Stacks and Queues Ch 6: Sorting Techniques →