Understanding Searching Algorithms

Introduction

Searching algorithms allow us to find the position of a specific element inside a collection of data. Searching is a fundamental operation in computer science, used in:

• Databases

• Search engines

• File systems

• User interfaces (search bars)

There are two major types of searching algorithms:

1. Linear Search

2. Binary Search

Let’s explore each one in detail.

Linear Search

Linear search is the simplest searching algorithm. It checks each element one by one until the target is found.

When to Use Linear Search

• The list is unsorted

• The list is very small

• Simplicity is more important than speed

How It Works

[5, 10, 15, 20, 25]
Search for 20:
Check 5 ? 10 ? 15 ? 20 ? Found

Time Complexity

• Best case: O(1)

• Worst case: O(n)

• Average: O(n)

C# Example

int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }
    return -1;
}

Binary Search

Binary search is a very efficient search algorithm but works only on sorted arrays.

It repeatedly divides the search space into halves.

How It Works

Sorted array: [5, 10, 15, 20, 25, 30]
Search 20:
Mid = 15 ? 20 > 15 ? search right half
Mid = 25 ? 20 < 25 ? search left half
Mid = 20 ? Found

Why Binary Search Is Fast

At each step, the search area is halved.

Examples:

• Start with 64 elements ? 6 steps

• Start with 1024 elements ? 10 steps

Time Complexity

• Best case: O(1)

• Worst case: O(log n)

• Average: O(log n)

C# Example

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

Linear Search vs Binary Search

Binary search is always preferred when the data is sorted.

Real-Life Applications of Searching Algorithms

Linear Search

• Finding a contact on your phone (unsorted list)

• Searching in small sets of data

Binary Search

• Dictionary word lookup

• Searching in a sorted product list

• Checking login credentials (binary search tree / hashed structures)

• File systems indexing

Why Searching Matters in DSA

Understanding searching helps you learn:

• Arrays

• Trees

• Hashing

• Graph algorithms

Searching is also the foundation for more advanced techniques like:

• Binary Search Trees

• Balanced Trees (AVL, Red-Black)

• Heaps

• Divide and Conquer algorithms

Example Problem: Find First and Last Occurrence (Binary Search Logic)

int FirstOccurrence(int[] arr, int target)
{
    int left = 0, right = arr.Length - 1, result = -1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
        {
            result = mid;
            right = mid - 1; // search left part
        }
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return result;
}

This type of problem is common in coding interviews.

Summary

Searching is a fundamental operation that appears across all areas of computer science. Understanding search algorithms helps you write faster, more efficient code.

Key takeaways:

• Linear Search ? Works on unsorted lists, but is slow

• Binary Search ? Requires sorted data but is extremely fast

• Searching is used in indexing, databases, and system-level operations