searching algorithms

Searching algorithms are systematic methods for locating specific data items within a data structure. Cambridge A-Level Computer Science focuses on two fundamental approaches:

Linear Search (Sequential Search) examines each element in a list sequentially until the target is found or the end is reached. It works on both sorted and unsorted data. Time Complexity: O(n) where n = number of elements. Best case: O(1) when target is first element; worst case: O(n) when target is last or absent.

Binary Search is a divide-and-conquer algorithm that repeatedly halves the search space. Prerequisites: Data MUST be sorted. The algorithm compares the target with the middle element, then eliminates half the remaining elements based on whether the target is greater or smaller. Time Complexity: O(log₂n) — dramatically faster for large datasets.

Key Formula for Binary Search:

mid = (low + high) // 2

where low and high are boundary indices.

Comparative Analysis:

• Linear Search: Simple implementation, no preprocessing required, suitable for small/unsorted datasets
• Binary Search: Requires sorted data, significantly faster O(log₂n) vs O(n), ideal for large datasets

Cambridge Definition: A searching algorithm is a step-by-step procedure for locating a particular value within a collection of data.

Mnemonic for Binary Search: "HALVE and CONQUER" — each iteration Halves the search space, ensuring Logarithmic time complexity.

Important: Candidates must understand when to apply each algorithm and justify their choice using complexity analysis — a common exam requirement.

Linear Search in Real Life: Imagine searching for a specific book on an unsorted bookshelf. You start at one end and examine each book sequentially until you find the target or reach the other end. This mirrors linear search perfectly — simple but potentially time-consuming for large collections.

Real Application: Contact lists on basic mobile phones use linear search when names aren't alphabetically sorted. Email spam filters employ linear search to check each message against blacklisted addresses in small databases.

Binary Search Analogy: Think of guessing a number between 1-100. The optimal strategy? Guess 50. If told "higher," guess 75 (middle of 51-100). This halving strategy is binary search. Another analogy: finding a word in a dictionary — you open to the middle, determine which half contains your word, and repeat.

Real Application: Database indexing systems use binary search trees for rapid data retrieval. When you search for a product on e-commerce platforms like Amazon, binary search algorithms quickly locate items in massive sorted inventories. Autocomplete features in search engines utilize binary search on sorted suggestion lists.

Why Binary Search Dominates: For 1 million records, linear search requires up to 1,000,000 comparisons (worst case), while binary search needs only log₂(1,000,000) ≈ 20 comparisons — a 50,000x improvement!

The Sorting Trade-off: Binary search requires preprocessing (sorting), which takes O(n log n) time. Therefore, for single searches on small unsorted datasets, linear search may actually be more efficient overall. However, for repeated searches, the sorting cost is amortized.

Cambridge Context: Exam questions often ask you to evaluate which algorithm suits specific scenarios — consider data size, whether data is sorted, and frequency of searches.