Searching Algorithms

Searching is finding a target value within a collection. The two fundamental approaches are linear search and binary search.

Linear Search — O(n)

Check every element from start to end. Works on any collection, sorted or not:

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

int[] data = { 7, 3, 9, 1, 5 };
Console.WriteLine(LinearSearch(data, 9)); // 2
Console.WriteLine(LinearSearch(data, 4)); // -1

Binary Search — O(log n)

Requires a sorted array. Repeatedly divide the search space in half:

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

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

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

    return -1; // not found
}

int[] sorted = { 1, 3, 5, 7, 9, 11, 13 };
Console.WriteLine(BinarySearch(sorted, 7));  // 3
Console.WriteLine(BinarySearch(sorted, 8));  // -1

Why Binary Search is Powerful

For 1 million elements: - Linear search: up to 1,000,000 comparisons - Binary search: at most 20 comparisons (log2 of 1M)

Built-in Methods

int[] sorted = { 1, 3, 5, 7, 9 };

// Array.BinarySearch — returns index or negative value
int idx = Array.BinarySearch(sorted, 5); // 2

// List<T>.BinarySearch
var list = new List<int> { 1, 3, 5, 7, 9 };
int pos = list.BinarySearch(7); // 3

// LINQ (linear search under the hood)
bool exists = sorted.Contains(5);
int first = sorted.First(x => x > 4); // 5