Mastering Algorithms

Chapter 6: Searching Algorithms

Introduction to Searching

Searching is one of the most fundamental operations in computer science. Whether you're looking up a contact in your phone, finding a file on your computer, or querying a database, searching algorithms are at work. Understanding different searching techniques and when to use them is crucial for writing efficient code.

This chapter covers the two fundamental searching algorithms for arrays and lists: Linear Search and Binary Search. These algorithms form the foundation for searching in sorted and unsorted data structures. For graph traversal and pathfinding algorithms (DFS, BFS, Dijkstra's, Bellman-Ford, Floyd-Warshall, A*), see Chapter 7: Graph Algorithms.

Prerequisites: Before studying Binary Search, you should understand sorting algorithms (see Chapter 5: Sorting Algorithms), as Binary Search requires sorted data.

Searching Algorithms

1. Linear Search

The simplest searching algorithm that sequentially checks each element in a list until it finds the target value.

  • Time Complexity: O(n) worst/average, O(1) best
  • Space Complexity: O(1)
  • Best For: Unsorted data, small datasets
  • Prerequisites: None

2. Binary Search

An efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

  • Time Complexity: O(log n)
  • Space Complexity: O(1) iterative, O(log n) recursive
  • Best For: Sorted data, large datasets
  • Prerequisites: Understanding of sorted arrays (see Sorting Algorithms)

Algorithm Comparison

Here's a comparison of the two fundamental searching algorithms for arrays and lists:

Algorithm Data Structure Time Complexity Space Complexity Best Use Case
Linear Search Array/List O(n) O(1) Unsorted data, small datasets
Binary Search Sorted Array O(log n) O(1) iterative, O(log n) recursive Sorted arrays, large datasets

Algorithm Selection Guide

When to Use Linear Search:

  • Data is unsorted
  • Dataset is small (n < 100)
  • You only need to search once
  • Data structure doesn't support random access

When to Use Binary Search:

  • Data is sorted (or can be sorted)
  • Dataset is large (n > 100)
  • You need to perform multiple searches
  • Data structure supports random access

Note: For graph traversal and pathfinding algorithms (DFS, BFS, Dijkstra's, Bellman-Ford, Floyd-Warshall, A*), see Chapter 7: Graph Algorithms.

What's Next?

Now that you understand fundamental searching algorithms, explore related topics: