Binary Search

Among the most popular search algorithms, binary search stands out for its remarkable efficiency and simplicity. This algorithm uses the divide et impera approach, which systematically halves the search space and is particularly efficient for large ordered datasets. The elegance of binary search lies not only in its efficiency, but also in its wide range of applications, from simple data retrieval to complex computational problems.

Implementations

Below is a simple implementation of the binary search algorithm and a possible optimisation of it.

👉 Binary Search

Binary search is a search algorithm designed for ordered lists. It works by repeatedly dividing the search range in half and comparing the central element of the range with the target value. If the central element is equal to the target value, the search is successful and the index of the central element is returned. If the central element is less than the target value, the search continues in the right half of the interval. If the central element is greater than the target value, the search continues in the left half of the range. If the target value is not in the list, the algorithm returns a value indicating that the element was not found.

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

    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (array[middle] == target)
        {
            return middle;
        }

        if (array[middle] < target)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }

    return -1;
}

👉 Optimized Binary Search

A potential pitfall in the standard binary search algorithm is integer overflow when calculating the middle index using the formula (left + right) / 2. In cases where left and right are large integers, their sum may exceed the maximum representable integer value, causing an overflow and resulting in an incorrect middle index. To mitigate this issue, the optimized binary search algorithm uses the formula left + (right - left) / 2, which prevents overflow by first calculating the difference between right and left, ensuring that the sum remains within the representable integer range.

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

    while (left <= right)
    {
        int middle = left + (right - left) / 2;
        if (array[middle] == target)
        {
            return middle;
        }

        if (array[middle] < target)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
    }

    return -1;
}

Time complexity

The time complexity of the binary search algorithm is determined by the number of iterations it takes to find the target value or reduce the search interval to zero. Since the search interval is halved with each iteration, the time complexity of binary search is O(log n), where n is the number of elements in the list.

Space complexity

Binary search has a space complexity of O(1) because it only requires a constant amount of additional memory to store the left, right, and middle indices during the search process. This minimal space overhead makes binary search suitable for applications with limited memory resources or when space efficiency is a priority.

Conclusion

Binary search, recognized for its high efficiency, is particularly suitable for searching large datasets. It's relatively simple to understand and implement, and an additional advantage is its minimal need for extra memory during the search process. However, it does come with limitations, such as its reliance on sorted lists and relative inefficiency for small datasets. Despite these, when compared to a linear search on ordered data sets, binary search generally exhibits superior performance.

Utilizing the optimized version of the algorithm, which addresses potential issues such as integer overflow, can ensure more robust and reliable performance across a wide range of scenarios. This characteristic amplifies its appeal, marking binary search as a noteworthy algorithm in the field of data search.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)