Introduction to Binary Search in C#

Welcome to today's lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. We can find the targeted item by repeatedly dividing the search interval in half. It's akin to flipping through a dictionary— instead of going page by page, you'd start in the middle, then narrow down the section in half until you find your desired word.

Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target. For example, if looking for the number 8 in a sorted list ranging from 1 to 10, we would start at 5. Since 8 is larger than the midpoint, we narrow the search to the second half of the list, leaving us with numbers 6 to 10. In this new sublist, the middle number is 8, and thus, we've found our target. This efficient approach significantly reduces the number of comparisons needed compared to a linear search.

Let's see how Binary Search can be implemented in C#, taking a recursive approach. This process involves a function calling itself—with a base case in place to prevent infinite loops—and a recursive case to solve smaller parts of the problem.

public int BinarySearch(int[] arr, int start, int end, int target)
{
    if (start > end) return -1; // Base case
    
    int mid = start + (end - start) / 2; // Find the midpoint
    
    if (arr[mid] == target) return mid; // Target found
    
    if (arr[mid] > target) // If the target is less than the midpoint
        return BinarySearch(arr, start, mid - 1, target); // Search the left half
        
    return BinarySearch(arr, mid + 1, end, target); // Search the right half
}

In this C# code, the base case is defined first. If the start index is greater than the end index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, it’s returned. Depending on whether the target is less or more than the midpoint, the search continues within the left or right half, respectively.

Let's analyze the time complexity of Binary Search, which measures how much time an algorithm takes as the input size increases. Notably, Binary Search halves the list at every step, necessitating log(n) steps for an array of size n. Therefore, the time complexity of Binary Search is O(log n).