2 - Basic Searching Algorithms

Basic searching algorithms are fundamental techniques for finding elements in a collection. They form the foundation for more complex searching strategies and are essential for any programmer to understand.

Linear Search

Linear Search (also known as Sequential Search) is the simplest searching algorithm. It checks each element of the collection one by one until it finds the target element or reaches the end of the collection.

How It Works

Start from the first element of the collection.
Compare each element with the target value.
If the element matches the target, return its position.
If the end of the collection is reached without finding the target, return a value indicating that the element was not found (e.g., -1).

Implementation

/// <summary>
/// Performs a linear search on an array to find the specified target element.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IEquatable.</typeparam>
/// <param name="array">The array to search through.</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
public static int LinearSearch<T>(T[] array, T target) where T : IEquatable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    // Iterate through each element in the array
    for (int i = 0; i < array.Length; i++)
    {
        // Compare the current element with the target
        if (array[i].Equals(target))
        {
            return i; // Found the target at index i
        }
    }
    
    return -1; // Target not found in the array
}

For more flexibility with custom comparison logic:

/// <summary>
/// Performs a linear search on an array using a custom comparison function.
/// </summary>
/// <typeparam name="T">The type of elements in the array.</typeparam>
/// <param name="array">The array to search through.</param>
/// <param name="target">The element to find in the array.</param>
/// <param name="comparer">Optional custom comparison function; if null, default equality comparison is used.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
public static int LinearSearch<T>(T[] array, T target, Func<T, T, bool> comparer = null)
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    // If no custom comparer is provided, use the default equality comparer
    comparer ??= (a, b) => EqualityComparer<T>.Default.Equals(a, b);
    
    // Iterate through each element in the array
    for (int i = 0; i < array.Length; i++)
    {
        // Use the provided comparison function to check for a match
        if (comparer(array[i], target))
        {
            return i; // Found the target at index i
        }
    }
    
    return -1; // Target not found in the array
}

Optimizations

1. Early Termination

If we know the collection contains at most one occurrence of the target, we can return as soon as we find it:

/// <summary>
/// Checks if a target element exists in an array using linear search with early termination.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IEquatable.</typeparam>
/// <param name="array">The array to search through.</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>True if the target exists in the array; otherwise, false.</returns>
public static bool LinearSearchExists<T>(T[] array, T target) where T : IEquatable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    // Use foreach for cleaner iteration when we only need to check existence
    foreach (T element in array)
    {
        // Compare the current element with the target
        if (element.Equals(target))
        {
            return true; // Found the target, exit immediately
        }
    }
    
    return false; // Target not found after checking all elements
}

2. Sentinel Linear Search

By adding the target element at the end of the array, we can eliminate the need to check if we've reached the end of the array in each iteration:

/// <summary>
/// Performs a linear search using the sentinel technique to improve efficiency.
/// This method temporarily modifies the input array.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IEquatable.</typeparam>
/// <param name="array">The array to search through (will be temporarily modified).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
/// <remarks>
/// The sentinel technique eliminates the need for boundary checking in each iteration
/// by temporarily placing the target value at the end of the array.
/// </remarks>
public static int SentinelLinearSearch<T>(T[] array, T target) where T : IEquatable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    if (array.Length == 0)
        return -1; // Empty array case
    
    int n = array.Length;
    
    // Store the last element to restore it later
    T lastElement = array[n - 1];
    
    // Place the target as sentinel at the end of the array
    // This guarantees the loop will terminate without boundary checking
    array[n - 1] = target;
    
    int i = 0;
    // No need to check array bounds since we know we'll find the target
    // (either the real one or our sentinel)
    while (!array[i].Equals(target))
    {
        i++;
    }
    
    // Restore the original last element
    array[n - 1] = lastElement;
    
    // Determine if we found the actual target or just our sentinel
    if (i < n - 1 || lastElement.Equals(target))
    {
        return i; // Found the target at position i
    }
    
    return -1; // Target not found in the original array
}

Note: This optimization modifies the array temporarily, which might not be desirable in all cases.

3. Ordered Linear Search

If the collection is sorted, we can terminate early when we encounter an element greater than the target:

/// <summary>
/// Performs a linear search on a sorted array with early termination when passing the target value.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
/// <remarks>
/// This algorithm takes advantage of the sorted nature of the array to terminate early
/// when an element greater than the target is encountered, as all subsequent elements
/// will also be greater than the target.
/// </remarks>
public static int OrderedLinearSearch<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    for (int i = 0; i < array.Length; i++)
    {
        // Compare the current element with the target
        int comparisonResult = array[i].CompareTo(target);
        
        if (comparisonResult == 0)
        {
            return i; // Found the target at index i
        }
        
        // Early termination: if current element is greater than target,
        // then all subsequent elements will also be greater (in a sorted array)
        if (comparisonResult > 0)
        {
            return -1; // Target not found (all remaining elements are greater)
        }
    }
    
    return -1; // Target not found after checking all elements
}

Characteristics

Time Complexity:
- Best Case: O(1) when the target is the first element
- Average Case: O(n/2) ≈ O(n)
- Worst Case: O(n) when the target is the last element or not present
Space Complexity: O(1) - no additional space required
Advantages:
- Simple to implement
- Works on unsorted collections
- No preprocessing required
- In-place algorithm
Disadvantages:
- Inefficient for large collections
- Doesn't take advantage of sorted data (unless modified)

When to Use

Small collections where the overhead of more complex algorithms isn't justified
Unsorted collections where sorting would be more expensive than linear search
Collections that are searched infrequently
When simplicity is more important than efficiency

Binary Search

Binary Search is an efficient algorithm for finding an element in a sorted collection. It repeatedly divides the search space in half, eliminating half of the remaining elements at each step.

How It Works

Start with the middle element of the sorted collection.
If the target equals the middle element, return its position.
If the target is less than the middle element, search the left half.
If the target is greater than the middle element, search the right half.
Repeat steps 1-4 until the target is found or the search space is empty.

Implementation

Iterative Approach

/// <summary>
/// Performs a binary search on a sorted array to find the specified target element.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
/// <exception cref="ArgumentNullException">Thrown when the array is null.</exception>
/// <remarks>
/// Binary search has O(log n) time complexity, making it much more efficient than
/// linear search for large sorted arrays. It works by repeatedly dividing the search
/// interval in half.
/// </remarks>
public static int BinarySearch<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    int left = 0;
    int right = array.Length - 1;
    
    // Continue searching while there are elements to check
    while (left <= right)
    {
        // Calculate middle index using this formula to avoid integer overflow
        // that could occur with (left + right) / 2
        int mid = left + (right - left) / 2;
        
        // Compare the middle element with the target
        int comparison = target.CompareTo(array[mid]);
        
        if (comparison == 0)
        {
            return mid; // Found the target at index mid
        }
        
        if (comparison < 0)
        {
            // Target is smaller than the middle element, search in the left half
            right = mid - 1;
        }
        else
        {
            // Target is larger than the middle element, search in the right half
            left = mid + 1;
        }
    }
    
    return -1; // Target not found in the array
}

Recursive Approach

/// <summary>
/// Performs a binary search on a sorted array using a recursive approach.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
/// <exception cref="ArgumentNullException">Thrown when the array is null.</exception>
public static int BinarySearchRecursive<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    // Call the recursive helper method with the full array range
    return BinarySearchRecursiveHelper(array, target, 0, array.Length - 1);
}

/// <summary>
/// Helper method that performs the recursive binary search on a specified range of the array.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through.</param>
/// <param name="target">The element to find in the array.</param>
/// <param name="left">The left boundary of the search range (inclusive).</param>
/// <param name="right">The right boundary of the search range (inclusive).</param>
/// <returns>The index of the target if found; otherwise, -1.</returns>
private static int BinarySearchRecursiveHelper<T>(T[] array, T target, int left, int right) where T : IComparable<T>
{
    // Base case: if the search range is empty, the target is not in the array
    if (left > right)
    {
        return -1; // Target not found
    }
    
    // Calculate middle index using this formula to avoid integer overflow
    int mid = left + (right - left) / 2;
    
    // Compare the middle element with the target
    int comparison = target.CompareTo(array[mid]);
    
    if (comparison == 0)
    {
        return mid; // Found the target at index mid
    }
    
    if (comparison < 0)
    {
        // Target is smaller than the middle element, search in the left half
        return BinarySearchRecursiveHelper(array, target, left, mid - 1);
    }
    
    // Target is larger than the middle element, search in the right half
    return BinarySearchRecursiveHelper(array, target, mid + 1, right);
}

Variations

1. Finding the First Occurrence

If the collection contains duplicate elements, the standard binary search might not return the first occurrence. Here's a modified version that finds the first occurrence:

/// <summary>
/// Performs a binary search on a sorted array to find the first occurrence of the target element.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the first occurrence of the target if found; otherwise, -1.</returns>
/// <exception cref="ArgumentNullException">Thrown when the array is null.</exception>
/// <remarks>
/// This variation of binary search is useful when the array may contain duplicate elements
/// and you need to find the first (leftmost) occurrence of the target value.
/// </remarks>
public static int BinarySearchFirstOccurrence<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    int left = 0;
    int right = array.Length - 1;
    int result = -1; // Will hold the index of the first occurrence if found
    
    while (left <= right)
    {
        // Calculate middle index
        int mid = left + (right - left) / 2;
        
        // Compare the middle element with the target
        int comparison = target.CompareTo(array[mid]);
        
        if (comparison == 0)
        {
            // Found an occurrence, but continue searching in the left half
            // to find the first occurrence
            result = mid;
            right = mid - 1;
        }
        else if (comparison < 0)
        {
            // Target is smaller than the middle element, search in the left half
            right = mid - 1;
        }
        else
        {
            // Target is larger than the middle element, search in the right half
            left = mid + 1;
        }
    }
    
    return result; // Returns -1 if target not found, otherwise the index of the first occurrence
}

2. Finding the Last Occurrence

Similarly, to find the last occurrence:

/// <summary>
/// Performs a binary search on a sorted array to find the last occurrence of the target element.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The element to find in the array.</param>
/// <returns>The index of the last occurrence of the target if found; otherwise, -1.</returns>
/// <exception cref="ArgumentNullException">Thrown when the array is null.</exception>
/// <remarks>
/// This variation of binary search is useful when the array may contain duplicate elements
/// and you need to find the last (rightmost) occurrence of the target value.
/// </remarks>
public static int BinarySearchLastOccurrence<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    int left = 0;
    int right = array.Length - 1;
    int result = -1; // Will hold the index of the last occurrence if found
    
    while (left <= right)
    {
        // Calculate middle index
        int mid = left + (right - left) / 2;
        
        // Compare the middle element with the target
        int comparison = target.CompareTo(array[mid]);
        
        if (comparison == 0)
        {
            // Found an occurrence, but continue searching in the right half
            // to find the last occurrence
            result = mid;
            left = mid + 1;
        }
        else if (comparison < 0)
        {
            // Target is smaller than the middle element, search in the left half
            right = mid - 1;
        }
        else
        {
            // Target is larger than the middle element, search in the right half
            left = mid + 1;
        }
    }
    
    return result; // Returns -1 if target not found, otherwise the index of the last occurrence
}

3. Finding the Closest Element

If the exact target isn't found, we might want to find the closest element:

/// <summary>
/// Performs a binary search on a sorted array to find the element closest to the target value.
/// </summary>
/// <typeparam name="T">The type of elements in the array, must implement IComparable.</typeparam>
/// <param name="array">The sorted array to search through (must be in ascending order).</param>
/// <param name="target">The target value to find or approximate.</param>
/// <returns>
/// The index of the element closest to the target value. If the array is empty, returns -1.
/// If multiple elements are equally close, returns the index of one of them.
/// </returns>
/// <exception cref="ArgumentNullException">Thrown when the array is null.</exception>
/// <remarks>
/// This algorithm is useful when you need to find the nearest match to a value
/// that might not exist exactly in the array. It works by first attempting a standard
/// binary search, and if the exact value isn't found, it compares the closest elements
/// on either side of where the target would be.
/// </remarks>
public static int BinarySearchClosest<T>(T[] array, T target) where T : IComparable<T>
{
    // Input validation
    if (array == null)
        throw new ArgumentNullException(nameof(array), "Array cannot be null");
    
    if (array.Length == 0)
        return -1; // Empty array case
    
    int left = 0;
    int right = array.Length - 1;
    
    // Special cases: target is outside the range of array values
    
    // If target is less than the smallest element, the closest is the first element
    if (target.CompareTo(array[0]) < 0)
        return 0;
    
    // If target is greater than the largest element, the closest is the last element
    if (target.CompareTo(array[right]) > 0)
        return right;
    
    // Standard binary search
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        
        int comparison = target.CompareTo(array[mid]);
        
        if (comparison == 0)
        {
            return mid; // Found the exact target
        }
        
        if (comparison < 0)
        {
            right = mid - 1; // Target is in the left half
        }
        else
        {
            left = mid + 1; // Target is in the right half
        }
    }
    
    // At this point, left > right
    // The closest element is either at index right or left
    
    // Handle edge cases
    if (right < 0)
        return left; // Target is smaller than all elements
    
    if (left >= array.Length)
        return right; // Target is larger than all elements
    
    // Compare the absolute differences to determine which element is closer
    // We need to be careful with the comparison here since CompareTo doesn't return
    // the actual difference but just -1, 0, or 1
    
    // Get the difference between target and the element at left
    int leftDiff = Math.Abs(target.CompareTo(array[left]));
    
    // Get the difference between target and the element at right
    int rightDiff = Math.Abs(target.CompareTo(array[right]));
    
    // Return the index of the element with the smaller difference
    return leftDiff < rightDiff ? left : right;
}

Characteristics

Time Complexity:
- Best Case: O(1) when the target is the middle element
- Average Case: O(log n)
- Worst Case: O(log n)
Space Complexity:
- Iterative: O(1)
- Recursive: O(log n) due to the call stack
Advantages:
- Very efficient for large collections
- Logarithmic time complexity
- Predictable performance
Disadvantages:
- Requires sorted collection
- Not suitable for collections that change frequently (due to sorting overhead)
- Not cache-friendly for large arrays (due to non-sequential memory access)

When to Use

Sorted collections or when the cost of sorting is justified by multiple searches
Large collections where efficiency is important
When the collection is relatively static (not frequently modified)
When memory usage is a concern (compared to more complex data structures)

Comparison of Basic Searching Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Preprocessing	Data Requirements
Linear Search	O(1)	O(n)	O(n)	O(1)	None	None
Binary Search	O(1)	O(log n)	O(log n)	O(1)	Sorting: O(n log n)	Sorted array

Performance Characteristics

Linear Search: Simple but inefficient for large collections; works on unsorted data.
Binary Search: Much more efficient for large collections but requires sorted data.

Practical Considerations

Implementation in C#

When implementing searching algorithms in C#, consider:

Generic Implementation: Use generics to make your searching algorithm work with any comparable type.
Comparison Delegates: Allow custom comparison logic through delegates or lambda expressions.
Error Handling: Decide how to handle cases where the element is not found.
Edge Cases: Handle empty collections, single-element collections, and other special cases.

Built-in Searching in .NET

.NET provides efficient built-in searching methods:

// For arrays
int index = Array.IndexOf(myArray, target); // Linear search
int index = Array.BinarySearch(myArray, target); // Binary search (array must be sorted)

// For lists
int index = myList.IndexOf(target); // Linear search
int index = myList.BinarySearch(target); // Binary search (list must be sorted)

// With LINQ
bool exists = myCollection.Contains(target); // Linear search
int index = myCollection.ToList().IndexOf(target); // Linear search

Choosing Between Linear and Binary Search

As a rule of thumb:

Use Linear Search when:
- The collection is small (roughly < 100 elements)
- The collection is unsorted and sorting would be expensive
- The collection is searched infrequently
- The collection changes frequently
Use Binary Search when:
- The collection is large
- The collection is already sorted or can be sorted once and searched multiple times
- Search efficiency is critical
- The collection is relatively static

Conclusion

Basic searching algorithms form the foundation of data retrieval in computer science. While Linear Search is simple and works on any collection, Binary Search offers significantly better performance for sorted collections. Understanding these algorithms and their characteristics allows you to choose the right tool for your specific requirements, balancing factors like collection size, sort state, and search frequency.

Linear Search​

How It Works​

Implementation​

Optimizations​

1. Early Termination​

2. Sentinel Linear Search​

3. Ordered Linear Search​

Characteristics​

When to Use​

Binary Search​

How It Works​

Implementation​

Iterative Approach​

Recursive Approach​

Variations​

1. Finding the First Occurrence​

2. Finding the Last Occurrence​

3. Finding the Closest Element​

Characteristics​

When to Use​

Comparison of Basic Searching Algorithms​

Performance Characteristics​

Practical Considerations​

Implementation in C#​

Built-in Searching in .NET​

Choosing Between Linear and Binary Search​

Conclusion​

Linear Search

How It Works

Implementation

Optimizations

1. Early Termination

2. Sentinel Linear Search

3. Ordered Linear Search

Characteristics

When to Use

Binary Search

How It Works

Implementation

Iterative Approach

Recursive Approach

Variations

1. Finding the First Occurrence

2. Finding the Last Occurrence

3. Finding the Closest Element

Characteristics

When to Use

Comparison of Basic Searching Algorithms

Performance Characteristics

Practical Considerations

Implementation in C#

Built-in Searching in .NET

Choosing Between Linear and Binary Search

Conclusion