6.7 Data Searches | Impacts Of Computing | Computer Science 11

Data searches are fundamental techniques used to locate specific information within a dataset. This topic covers two core search algorithms — Linear Search and Binary Search — as well as approaches for collecting original data.

1. Linear Search (Sequential Search)

Linear Search is the simplest search algorithm. It examines each element in a list one by one, from the first element to the last, until the target value is found or the entire list has been checked.

How It Works

Start at the first element.
Compare the current element with the target.
If they match → found.
If not → move to the next element.
If the end of the list is reached without a match → not found.

Characteristics

Feature	Detail
Works on	Sorted or unsorted data
Best case	$O (1)$ — target is the first element
Worst case	$O (n)$ — target is last or not present
Use case	Small lists or unsorted data

Example

Searching for 7 in the list [3, 9, 1, 7, 5]:

Check 3 → No
Check 9 → No
Check 1 → No
Check 7 → Found (4 comparisons)

2. Binary Search

Binary Search is a much faster algorithm, but it requires the dataset to be sorted first. It works by repeatedly halving the search space.

How It Works

Find the middle element of the sorted list.
If the middle element equals the target → found.
If the target is less than the middle → search the left half.
If the target is greater than the middle → search the right half.
Repeat until found or the search space is empty.

Characteristics

Feature	Detail
Prerequisite	Data must be sorted
Best case	$O (1)$ — target is the middle element
Worst case	$O (lo g n)$ — halving continues until found
Use case	Large sorted datasets

Example

Searching for 7 in the sorted list [1, 3, 5, 7, 9]:

Middle = 5 → 7 > 5, search right half [7, 9]
Middle = 7 → Found (2 comparisons)

Key Formula

For a list of $n$ elements, the maximum number of comparisons in Binary Search is: $Max comparisons = ⌈ lo g_{2} n ⌉$

For example, for $n = 1024$ : $lo g_{2} (1024) = 10$ comparisons maximum.

3. Comparing Linear vs Binary Search

Feature	Linear Search	Binary Search
Data requirement	Any (sorted or unsorted)	Must be sorted
Time complexity (worst)	$O (n)$	$O (lo g n)$
Efficiency on large data	Poor	Excellent
Implementation complexity	Simple	Moderate

4. Advanced Searches & Data-Collection Approaches

Beyond algorithmic searches, researchers often need to gather original (primary) data when existing data is insufficient. This requires designing a data-collection approach.

Primary Data-Collection Methods

a) Qualitative Interviews

Researcher asks open-ended questions to participants.
Produces in-depth, descriptive responses.
Example: Interviewing students about their learning preferences.

b) Surveys and Questionnaires

A structured set of questions distributed to many respondents.
Can be online (Google Forms) or paper-based.
Produces quantitative or qualitative data.
Example: A survey asking 200 students to rate their internet access.

c) Prototypes

A working model of a system or product built to test a concept.
Allows observation of how users interact with a design.
Example: Building a simple app prototype to test usability.

d) Simulations

A computer-based model that mimics real-world processes.
Used when real experiments are too costly, dangerous, or time-consuming.
Example: Simulating traffic flow to study congestion patterns.

Choosing the Right Approach

Goal	Recommended Method
Understand opinions/feelings	Qualitative interviews
Collect data from many people	Surveys
Test a design concept	Prototype
Model a complex system	Simulation

Summary

Linear Search: Simple, works on any list, $O (n)$ worst case.
Binary Search: Fast, requires sorted data, $O (lo g n)$ worst case.
Primary data collection methods include interviews, surveys, prototypes, and simulations — chosen based on the research goal.

1. Linear Search (Sequential Search)

How It Works

Start at the first element.
Compare the current element with the target.
If they match → found.
If not → move to the next element.
If the end of the list is reached without a match → not found.

Characteristics

Feature	Detail
Works on	Sorted or unsorted data
Best case	$O (1)$ — target is the first element
Worst case	$O (n)$ — target is last or not present
Use case	Small lists or unsorted data

Example

Searching for 7 in the list [3, 9, 1, 7, 5]:

Check 3 → No
Check 9 → No
Check 1 → No
Check 7 → Found (4 comparisons)

2. Binary Search

Binary Search is a much faster algorithm, but it requires the dataset to be sorted first. It works by repeatedly halving the search space.

How It Works

Find the middle element of the sorted list.
If the middle element equals the target → found.
If the target is less than the middle → search the left half.
If the target is greater than the middle → search the right half.
Repeat until found or the search space is empty.

Characteristics

Feature	Detail
Prerequisite	Data must be sorted
Best case	$O (1)$ — target is the middle element
Worst case	$O (lo g n)$ — halving continues until found
Use case	Large sorted datasets

Example

Searching for 7 in the sorted list [1, 3, 5, 7, 9]:

Middle = 5 → 7 > 5, search right half [7, 9]
Middle = 7 → Found (2 comparisons)

Key Formula

For a list of $n$ elements, the maximum number of comparisons in Binary Search is: $Max comparisons = ⌈ lo g_{2} n ⌉$

For example, for $n = 1024$ : $lo g_{2} (1024) = 10$ comparisons maximum.

3. Comparing Linear vs Binary Search

Feature	Linear Search	Binary Search
Data requirement	Any (sorted or unsorted)	Must be sorted
Time complexity (worst)	$O (n)$	$O (lo g n)$
Efficiency on large data	Poor	Excellent
Implementation complexity	Simple	Moderate

Researcher asks open-ended questions to participants.
Produces in-depth, descriptive responses.
Example: Interviewing students about their learning preferences.

b) Surveys and Questionnaires

A structured set of questions distributed to many respondents.
Can be online (Google Forms) or paper-based.
Produces quantitative or qualitative data.
Example: A survey asking 200 students to rate their internet access.

c) Prototypes

A working model of a system or product built to test a concept.
Allows observation of how users interact with a design.
Example: Building a simple app prototype to test usability.

d) Simulations

A computer-based model that mimics real-world processes.
Used when real experiments are too costly, dangerous, or time-consuming.
Example: Simulating traffic flow to study congestion patterns.

Choosing the Right Approach

Goal	Recommended Method
Understand opinions/feelings	Qualitative interviews
Collect data from many people	Surveys
Test a design concept	Prototype
Model a complex system	Simulation

Summary

Linear Search: Simple, works on any list, $O (n)$ worst case.
Binary Search: Fast, requires sorted data, $O (lo g n)$ worst case.
Primary data collection methods include interviews, surveys, prototypes, and simulations — chosen based on the research goal.