Phase 4: Algorithms

Module 21: Searching

Learning Objectives

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

• Understand the importance of searching algorithms.
• Learn Linear Search and Binary Search.
• Understand Binary Search on Answer.
• Analyze time and space complexity.
• Solve common interview problems using searching.
• Implement efficient search algorithms in C.

Introduction

Searching is one of the most fundamental operations in Computer Science.

A searching algorithm helps locate an element within a collection of data such as an array, linked list, or database.

Efficient searching is essential for:

• Databases
• Search Engines
• File Systems
• Operating Systems
• E-commerce Websites
• GPS Applications
• Social Media Platforms

What is Searching?

Searching is the process of finding the position of a target element in a collection.

Example

textCopy
1Array
2
310 20 30 40 50
4
5Target = 30

Output

textCopy
1Found at Index 2

Types of Searching

The two most common searching algorithms are:

• Linear Search
• Binary Search

Linear Search

Linear Search checks each element one by one until the target is found or the array ends.

Example

textCopy
1Array
2
315 22 18 35 40
4
5Target = 35

Steps

textCopy
115 ❌
2
322 ❌
4
518 ❌
6
735 ✅

Found after checking four elements.

Linear Search Algorithm

1. Start from the first element.
2. Compare the current element with the target.
3. If they are equal, return the index.
4. Otherwise, move to the next element.
5. If the end of the array is reached, return -1.

Linear Search Program

cCopy
1#include <stdio.h>
2
3int linearSearch(int arr[], int n, int target)
4{
5    for(int i = 0; i < n; i++)
6    {
7        if(arr[i] == target)
8            return i;
9    }
10
11    return -1;
12}
13
14int main()
15{
16    int arr[] = {10,20,30,40,50};
17    int n = sizeof(arr)/sizeof(arr[0]);
18
19    int target = 30;
20
21    int index = linearSearch(arr, n, target);
22
23    if(index != -1)
24        printf("Element found at index %d\n", index);
25    else
26        printf("Element not found\n");
27
28    return 0;
29}

Output

textCopy
1Element found at index 2

Time Complexity

Space Complexity

textCopy
1O(1)

Advantages

• Simple to implement.
• Works on both sorted and unsorted arrays.
• No preprocessing required.

Disadvantages

• Slow for large datasets.
• Checks every element in the worst case.

Binary Search

Binary Search is a much faster searching algorithm.

Requirement: The array must be sorted.

Instead of checking every element, Binary Search repeatedly divides the search space into two halves.

Example

textCopy
1Array
2
310 20 30 40 50 60 70
4
5Target = 50

Step 1

textCopy
1Middle = 40
2
3Target > 40
4
5Search Right Half

Step 2

textCopy
150 60 70
2
3Middle = 60
4
5Target < 60
6
7Search Left Half

Step 3

textCopy
150 ✅

Binary Search Algorithm

1. Set low = 0 and high = n - 1.
2. Find the middle element.
3. If the target equals the middle element, return the index.
4. If the target is smaller, search the left half.
5. If the target is larger, search the right half.
6. Repeat until the element is found or the search space becomes empty.

Binary Search Program

cCopy
1#include <stdio.h>
2
3int binarySearch(int arr[], int n, int target)
4{
5    int low = 0;
6    int high = n - 1;
7
8    while(low <= high)
9    {
10        int mid = low + (high - low) / 2;
11
12        if(arr[mid] == target)
13            return mid;
14
15        if(arr[mid] < target)
16            low = mid + 1;
17        else
18            high = mid - 1;
19    }
20
21    return -1;
22}
23
24int main()
25{
26    int arr[] = {10,20,30,40,50,60,70};
27    int n = sizeof(arr)/sizeof(arr[0]);
28
29    int target = 50;
30
31    int index = binarySearch(arr, n, target);
32
33    if(index != -1)
34        printf("Element found at index %d\n", index);
35    else
36        printf("Element not found\n");
37
38    return 0;
39}

Output

textCopy
1Element found at index 4

Binary Search Visualization

textCopy
1Array
2
310 20 30 40 50 60 70
4
5Low = 0
6
7High = 6
8
9↓
10
11Middle = 3
12
1340
14
15↓
16
17Target > 40
18
19↓
20
21Search Right
22
23↓
24
2550 60 70
26
27↓
28
29Middle = 5
30
3160
32
33↓
34
35Target < 60
36
37↓
38
39Search Left
40
41↓
42
4350
44
45Found

Why Use low + (high - low) / 2?

Instead of:

cCopy
1mid = (low + high) / 2;

Use:

cCopy
1mid = low + (high - low) / 2;

This prevents integer overflow when low and high are very large.

Binary Search Complexity

Space Complexity (Iterative)

textCopy
1O(1)

Recursive Version

textCopy
1O(log n)

Linear Search vs Binary Search

Binary Search on Answer

Binary Search on Answer is an optimization technique used when the answer lies within a range of values rather than directly in an array.

Instead of searching for an element, we search for the minimum or maximum valid answer.

General Steps

1. Define the search range.
2. Compute the middle value.
3. Check whether the middle value satisfies the condition.
4. Narrow the search space.
5. Repeat until the optimal answer is found.

Applications

• Minimum Eating Speed
• Allocate Minimum Pages
• Aggressive Cows
• Ship Packages Within D Days
• Painter's Partition Problem

Binary Search on Answer Example

Problem

Find the square root of a number (integer part).

Input

textCopy
1Number = 36

Search Range

textCopy
10 to 36

Middle

textCopy
118
2
318 × 18 > 36
4
5Search Left

Repeat until the answer becomes 6.

Time Complexity

textCopy
1O(log n)

Practice Problem 1: Search Insert Position

Problem

Given a sorted array, return the index if the target exists.

If it does not exist, return the position where it should be inserted.

Input

textCopy
1Array
2
31 3 5 6
4
5Target = 5

Output

textCopy
12

Input

textCopy
1Target = 2

Output

textCopy
11

Approach

• Use Binary Search.
• If the element is not found, return the low index.

Time Complexity

textCopy
1O(log n)

Practice Problem 2: Peak Element

A Peak Element is an element greater than or equal to its neighbors.

Example

textCopy
11 3 20 4 1

Peak

textCopy
120

Approach

• Compare the middle element with its neighbors.
• Move toward the larger neighbor.
• Continue until a peak is found.

Time Complexity

textCopy
1O(log n)

Real-World Applications

Search Engines

Search indexes use efficient search algorithms to retrieve results quickly.

Dictionary Applications

Binary Search helps locate words in sorted dictionaries.

Library Management

Book records are searched efficiently using sorted indexes.

E-commerce

Product catalogs use searching algorithms to locate items based on IDs or names.

Databases

Database indexing structures rely on efficient search techniques for fast data retrieval.

Common Interview Questions

1. Implement Linear Search.
2. Implement Binary Search (Iterative).
3. Implement Binary Search (Recursive).
4. Find the first occurrence of an element.
5. Find the last occurrence of an element.
6. Count occurrences of an element in a sorted array.
7. Find the Search Insert Position.
8. Find a Peak Element.
9. Explain Binary Search on Answer.
10. Find the square root of a number using Binary Search.

Common Mistakes to Avoid

• Applying Binary Search to an unsorted array.
• Using (low + high) / 2 without considering integer overflow.
• Forgetting to update low or high, leading to infinite loops.
• Incorrectly handling edge cases such as empty arrays or single-element arrays.
• Returning the wrong insertion position when the target is not found.

Best Practices

• Use Linear Search for small or unsorted datasets.
• Prefer Binary Search for large sorted datasets.
• Always calculate the middle index using low + (high - low) / 2.
• Clearly define the search space before implementing Binary Search on Answer.
• Test your implementation with boundary cases such as the first element, last element, and missing elements.
• Analyze both time and space complexity before choosing a searching algorithm.

Module Summary

In this module, you learned:

• What searching algorithms are and why they are essential.
• How Linear Search works on both sorted and unsorted arrays.
• How Binary Search efficiently searches sorted arrays using the divide-and-conquer approach.
• The concept of Binary Search on Answer for optimization problems.
• How to solve practical problems such as Search Insert Position and Peak Element.
• Real-world applications of searching algorithms in databases, search engines, and software systems.

After completing this module, you'll be ready to learn Sorting Algorithms, where you'll study Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Counting Sort, Radix Sort, and advanced sorting techniques used in competitive programming and software engineering.