Binary search algorithm

Introduction:

In the world of computer science and programming, search algorithms play a crucial role in efficiently finding specific values within a given dataset. One such algorithm that stands out for its efficiency is the binary search algorithm. In this article, we will explore the binary search algorithm in detail, its inner workings, and provide code examples in popular programming languages like C#, JavaScript, Python, and PHP.
What is the Binary Search Algorithm?
The binary search algorithm is a divide-and-conquer algorithm used to locate the position of a target value within a sorted array. It achieves this by repeatedly dividing the search space in half until the target value is found or determined to be absent. This algorithm is highly efficient, especially when dealing with large datasets, as it eliminates half of the remaining search space with each iteration.

Understanding the Binary Search Algorithm:

To better understand how the binary search algorithm works, let’s walk through the steps involved:

Start with a sorted array: The binary search algorithm requires the input array to be sorted in ascending or descending order. If the array is not sorted, it needs to be sorted beforehand.

Set the low and high pointers: Initially, the low pointer is set to the first element of the array, and the high pointer is set to the last element.

Compute the middle index: Calculate the middle index by taking the average of the low and high pointers. This will give us the index of the middle element.

Compare the target value with the middle element: If the target value is equal to the middle element, the search is successful, and the algorithm terminates. If the target value is less than the middle element, we update the high pointer to be one less than the middle index. If the target value is greater than the middle element, we update the low pointer to be one more than the middle index.

Repeat steps 3 and 4: We repeat steps 3 and 4 until the target value is found or until there are no more elements to search (low pointer becomes greater than the high pointer).

Links

Code Examples

C#
public int BinarySearch(int[] array, int target)
{
    int low = 0;
    int high = array.Length - 1;

    while (low <=high)
    {
        int middle = (low + high) / 2;

        if (array[middle] == target)
        {
            return middle;
        }
        else if (array[middle] < target)
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }

    return -1; // Target value not found
}

JavaScript
function binarySearch(array, target) {
    let low = 0;
    let high = array.length - 1;

    while (low <= high) {
        let middle = Math.floor((low + high) / 2);

        if (array[middle] === target) {
            return middle;
        } else if (array[middle] < target) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }

    return -1; // Target value not found
}

Python
def binary_search(array, target):
    low = 0
    high = len(array) - 1

    while low <= high:
        middle = (low + high) // 2

        if array[middle] == target:
            return middle
        elif array[middle] < target:
            low = middle + 1
        else:
            high = middle - 1

    return -1  # Target value not found

PHP
function binarySearch($array, $target) {
    $low = 0;
    $high = count($array) - 1;

    while ($low <= $high) {
        $middle = floor(($low + $high) / 2);

        if ($array[$middle] == $target) {
            return $middle;
        } elseif ($array[$middle] < $target) {
            $low = $middle + 1;
        } else {
            $high = $middle - 1;
        }
    }

    return -1; // Target value not found
}

Conclusion