Algorithms — Binary Search

Binary Search is a highly efficient algorithm used to find an element in a sorted collection. It uses the divide and conquer approach, reducing the problem size in half on each step. This algorithm is very useful to perform search operations in large datasets. In this article, I present how this algorithm works and how to use it, using code examples in .NET.

When Binary Search is Usefull

Suppose you have a collection of 10 elements, and you need to find a specific element. For that, you could use Linear Search, where the search process involves iterating through each element in the collection one by one, and it has a time complexity of O(n), meaning the time taken grows linearly with the size of the collection. For small collections, this method works well. However, as the size of the collection increases to thousands or even millions of elements, Linear Search becomes inefficient because it must potentially examine each element. In such cases, Binary Search is a much more efficient alternative.

If you want to know more about Big O Notations, please check this article.

Binary Search operates with a time complexity of O(log n) (where n is the number of elements in the array) which dramatically reduces the number of comparisons needed by repeatedly dividing the search interval in half. This makes Binary Search much faster than Linear Search for large datasets, as it quickly narrows down the possible locations of the target element. Thus, while Linear Search may be sufficient for small collections, Binary Search is far superior for handling large collections due to its significantly faster performance.

Below you can see a comparison table of Linear Search and Binary Search:

Considerations

There are two main conditions for using a Binary Search algorithm:

• The collection of elements needs to be sorted. If the collection is not sorted, the algorithm will not work.
• The data structure must allow direct access to its elements in constant time — O(1). This is possible when we have an Array or a List, but is not possible in other data structures such as Linked List.

How Binary Search Works

Binary Search algorithm repeatedly divides the search interval in half and compares the target value to the middle element of the array, if the middle element is not the searched value, it eliminates half of the remaining elements from consideration. This process continues until the target element is found or the search interval is empty.

On each search iteration, the algorithm compares the target value to the middle element of the current search range. Based on this comparison, it decides whether to continue searching in the left half or the right half of the array.

Important: There is more than one way to implement Binary Search, and sometimes you might need to apply a specific condition to determine if you are going to search next the left or the right side.

Find the Exact Value Approach

This Binary Search approach can be used when you need to find the exact position (index) of the target element in a sorted array. For example, consider the array below, which contains 9 elements, and the target element is the number 12, which is in the index 2:

The first time the algorithm is executed, it will set the Left and Right pointers for the search range, where Left is the leftmost position of the array, and Right is the rightmost position of the array. The it will calculate the Middle of the array, which in this example is index 4, and it will check if this is the target element:

The element in index 4, is the number 19, which is not the target element, and it is bigger than 12, so we know that the target element is in the left part of the array, and this means that the right part of the array can be discarded (including the middle index that was used in the search):

Then continue with the search, considering only the left side of the array. For that, it sets the value of Right to middle - 1, which in this case is 3, and Left remains with the same value, and then it calculates the Middle, which is now index 1:

Number 7 is now the current element, and it is lower than the target element, this means that we need to move to the right. For that, it sets the value of Left to middle + 1, which in this example will be 2, and Right remains 3. Then it calculates the Middle, which will be index 2, which is the target element we are searching:

Then we return the index of the target element:

Next, I’m going to present some common Binary Search algorithms. These are well-known algorithms that can be used to perform Binary Searches, I’m going to explain them step by step.

Find the Exact Value Algorithm

This is how you can implement this algorithm:

public static int FindExactValueApproach(int[] nums, int target)
{
    // Initialize the left and right pointers for the search range;
    var left = 0;
    var right = nums.Length - 1;

    // Perform binary search as long as the search range is valid;
    while (left <= right)
    {
        // Calculate the middle index of the current search range;
        // Continuously divide the search range in half until the target element is found or the search range becomes empty;
        var middle = left + (right - left) / 2; // It avoids potential overflow errors that might occur if simply calculating (left + right) / 2 when dealing with large arrays or very large integer values;

        // If the middle element is the target, return its index;
        if (nums[middle] == target) return middle;

        // If the target is greater than the middle element, search the right half;
        if (nums[middle] < target) left = middle + 1;

        // If the target is smaller than the middle element, search the left half;
        if (nums[middle] > target) right = middle - 1;
    }

    // If the target is not found, return -1;
    return -1;
}

1. This algorithm receives an array of numbers and a target value as parameters.
2. It starts with two pointers: left and right, representing the bounds of the search interval. left is initially set to index 0, and right is set to the last index (n - 1) of the array.
3. Then it executes a loop while left is lower or equal to right
4. Inside the loop, it dynamically calculates the middle index using the formula left + (right — left) / 2, to avoid overflow in case of large indices.
5. Then it compares the middle element with the target value:

• If it is equal to the target, return the index
• If it is lower than the target, move the left pointer to middle + 1, to search in the right half
• If it is greater than the target, move the right pointer to middle - 1, to search in the left half

6. The process continues until left exceeds right. If the target is not found until there, then the algorithm returns -1.

The Time complexity for this algorithm is O(log n), as nums is divided into half each time, and in the worst-case scenario, we need to cut nums until the range has no element, and it takes logarithmic time to reach this break condition. The Space complexity is O(1), during the loop, we only need to record three indexes, left, right, and mid, they take constant space.

Find the Exact Value — Recursive Approach

Another way to achieve the same result as the previous example, is by using Recursion:

public static int FindRecursiveApproach(int[] nums, int target, int left, int right)
{
    // If the search range is invalid, return -1;
    if (left > right) return -1;

    // Calculate the middle index of the current search range;
    var middle = left + (right - left) / 2;

    // If the middle element is the target, return its index;
    if (nums[middle] == target) return middle;

    // If the target is greater than the middle element, search the right half;
    if (nums[middle] < target)
    {
        return FindRecursiveApproach(nums, target, middle + 1, right);
    }
    // If the target is smaller than the middle element, search the left half;
    else
    {
        return FindRecursiveApproach(nums, target, left, middle - 1);
    }
}

The recursive approach has a Time Complexity of O(log n), similar to the non-recursive approach, and has a Space Complexity of O(log n), due to the recursive calls on the call stack.

Now let’s say you require handling more complex scenarios involving duplicates or boundary conditions in your search. In that case, you can use the Find Lower Bound or Found Upper bound approaches, which I present next.

Find the Lower Bound Approach

In this approach, it returns the leftmost position of the target element. This algorithm is useful when you have an array with duplicated elements, and you want to return the first position of the searched element:

public static int FindLowerBoundApproach(int[] nums, int target)
{
    // Initialize the left and right pointers for the search range;
    var left = 0;
    var right = nums.Length;

    // Continue the loop as long as the left boundary is less than the right boundary;
    while (left < right)
    {
        // Calculate the middle index of the current search range;
        var middle = left + (right - left) / 2;

        // If the middle element is greater than or equal to the target,
        // move the right boundary to middle;
        if (nums[middle] >= target)
        {
            right = middle;
        }
        // If the middle element is less than the target,
        // move the left boundary to the right of middle;
        else
        {
            left = middle + 1;
        }
    }

    // After exiting the loop, check if the left boundary element is equal to the target;
    if (left < nums.Length && nums[left] == target)
    {
        return left;
    }
    // If the target is not found, return -1;
    else
    {
        return -1;
    }
}

Find the Upper Bound Approach

In this approach, it returns the rightmost position of the target element. Similar to the previous approach, this algorithm is useful when you have an array with duplicated elements, and you want to return the last position of the searched element:

public static int FindUpperBoundApproach(int[] nums, int target)
{
    // Initialize the left and right pointers for the search range;
    var left = 0;
    var right = nums.Length;

    // Continue the loop as long as the left boundary is less than the right boundary;
    while (left < right)
    {
        // Calculate the middle index of the current search range;
        var middle = left + (right - left) / 2;

        // If the middle element is less than or equal to the target,
        // move the left boundary to the right of middle;
        if (nums[middle] <= target)
        {
            left = middle + 1;
        }
        // If the middle element is greater than the target,
        // move the right boundary to the middle;
        else
        {
            right = middle;
        }
    }

    // After exiting the loop, check if the element just before the left boundary
    // is equal to the target. If so, return its index;
    if (left > 0 && nums[left - 1] == target)
    {
        return left - 1;
    }
    // If the target is not found, return -1;
    else
    {
        return -1;
    }
}

Conclusion

Binary Search is an efficient algorithm for finding elements in sorted collections that contain a large number of elements. Its logarithmic Time Complexity — O(log n) makes it ideal for large datasets, providing significant performance improvements over linear search.

This is the link for the project in GitHub: https://github.com/henriquesd/BinarySearchDemo

If you like this demo, I kindly ask you to give a ⭐️ in the repository.

Thanks for reading