Search Algorithms Tutorial

Master the most commonly used search algorithms in computer science. This guide covers Linear Search, Binary Search, Depth-First Search (DFS), Breadth-First Search (BFS), and more, with step-by-step examples, time complexities, and space complexities for each.

1. Linear Search

Linear Search is the simplest search algorithm. It works by checking each element in the list sequentially until the target element is found or the list ends.

Time Complexity: O(n)

Space Complexity: O(1)

Linear Search Example:

List: [5, 3, 8, 4, 2]
Target: 4

Step 1: Compare with 5 (not a match)
Step 2: Compare with 3 (not a match)
Step 3: Compare with 8 (not a match)
Step 4: Compare with 4 (match found)

Result: Element found at index 3
        

2. Binary Search

Binary Search is an efficient algorithm for finding an element in a sorted list. It works by repeatedly dividing the search interval in half. If the target value is equal to the middle element, the search is successful. If the target value is less than the middle element, the search continues on the left half, and if it is greater, on the right half.

Time Complexity: O(log n)

Space Complexity: O(1) or O(log n) with recursion

Binary Search Example:

List: [2, 3, 4, 5, 8]
Target: 5

Step 1: Compare with middle element 4 (not a match)
Step 2: Target is greater, search in [5, 8]
Step 3: Compare with middle element 5 (match found)

Result: Element found at index 3
        

3. Depth-First Search (DFS)

Depth-First Search is an algorithm used for traversing or searching tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking.

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges

Space Complexity: O(V) for the recursive stack

DFS Example:

Graph:
1 - 2
|   |
3 - 4

DFS starting from node 1:
Step 1: Visit 1
Step 2: Visit 2
Step 3: Visit 4
Step 4: Visit 3

Result: Traversal order is [1, 2, 4, 3]
        

4. Breadth-First Search (BFS)

Breadth-First Search is an algorithm used for traversing or searching tree or graph data structures. It starts at the root node and explores all the neighbor nodes at the present depth level before moving on to nodes at the next depth level.

Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges

Space Complexity: O(V) for the queue

BFS Example:

Graph:
1 - 2
|   |
3 - 4

BFS starting from node 1:
Step 1: Visit 1
Step 2: Visit 2
Step 3: Visit 3
Step 4: Visit 4

Result: Traversal order is [1, 2, 3, 4]
        

5. Interpolation Search

Interpolation Search is an improvement over Binary Search for instances where the values in a sorted array are uniformly distributed. It works by probing the position of the target value based on the value of the array's elements.

Time Complexity: O(log log n) on average, O(n) in the worst case

Space Complexity: O(1)

Interpolation Search Example:

List: [10, 20, 30, 40, 50]
Target: 30

Step 1: Probing position based on value
Step 2: Directly find the target at index 2

Result: Element found at index 2
        

6. Jump Search

Jump Search is an algorithm for finding an element in a sorted list. It works by jumping ahead by fixed steps and then performing a linear search in a smaller range when the target is possibly found.

Time Complexity: O(√n)

Space Complexity: O(1)

Jump Search Example:

List: [1, 3, 5, 7, 9, 11, 13, 15]
Target: 9

Step 1: Jump 3 elements (land on 7)
Step 2: Jump 3 more elements (land on 13, too far)
Step 3: Perform linear search between 7 and 13
Step 4: Find 9

Result: Element found at index 4
        

7. Exponential Search

Exponential Search is an algorithm that starts by searching at the start of the list and exponentially increases the search range until it finds a range where the target element might be present, then switches to Binary Search in that range.

Time Complexity: O(log n)

Space Complexity: O(log n) with recursion

Exponential Search Example:

List: [2, 4, 8, 16, 32, 64, 128, 256]
Target: 64

Step 1: Start search at index 0, 1, 2, 4, 8 (exceeds target)
Step 2: Switch to Binary Search between indices 4 and 8

Result: Element found at index 5
        

8. Fibonacci Search

Fibonacci Search is a search algorithm that divides the array using Fibonacci numbers. It compares the target value with the element at the Fibonacci index and reduces the search size based on comparison results.

Time Complexity: O(log n)

Space Complexity: O(1)

Fibonacci Search Example:

List: [1, 3, 4, 7, 10, 14, 18, 21]
Target: 14

Step 1: Generate Fibonacci sequence up to list size
Step 2: Compare with element at Fibonacci index
Step 3: Narrow down the search range and repeat

Result: Element found at index 5
        

9. Ternary Search

Ternary Search is a search algorithm similar to Binary Search but divides the list into three parts instead of two and recursively searches in the appropriate third.

Time Complexity: O(log₃ n)

Space Complexity: O(log n) with recursion

Ternary Search Example:

List: [2, 4, 6, 8, 10, 12, 14, 16, 18]
Target: 12

Step 1: Divide the list into three parts
Step 2: Compare with elements at 1/3rd and 2/3rd positions
Step 3: Narrow down the range and continue search

Result: Element found at index 5
        

10. Sublist Search

Sublist Search is used to find if a smaller list exists within a larger list. It works by moving a sliding window over the larger list and checking for a match with the smaller list.

Time Complexity: O(n * m) where n is the size of the larger list and m is the size of the smaller list

Space Complexity: O(1)

Sublist Search Example:

Larger list: [1, 3, 5, 7, 9, 11, 13, 15]
Smaller list: [7, 9, 11]

Step 1: Move sliding window of size 3 over larger list
Step 2: Compare sublist with smaller list

Result: Sublist found starting at index 3
        

Conclusion

Each search algorithm has its strengths and weaknesses, and the best one to use often depends on the specific context or dataset you are working with. Understanding these algorithms is crucial for optimizing performance in various computational tasks.