Binary Search is one of the most elegant and efficient searching algorithms in Computer Science. It works on the principle of divide-and-conquer, repeatedly halving the search space until the target is found. This approach makes it dramatically faster than Linear Search for large, sorted datasets.

Imagine looking up a word in a physical dictionary. You would not start at page one and read every entry—that would take forever! Instead, you open the dictionary roughly in the middle. If your word comes before the page you opened, you focus on the first half; if it comes after, you focus on the second half. You keep halving until you find your word. This is exactly how Binary Search works.

The core mechanism of Binary Search relies on eliminating half of the remaining elements with each comparison.

• Prerequisite: The array must be sorted in ascending (or descending) order.
• Initialize: Set two pointers:left = 0right = n - 1
• Calculate Mid: Find the middle index:mid = (left + right) / 2
• Compare: Ifarr[mid] == target, the search is complete—return mid.
• Narrow Left: Ifarr[mid] < target, the target is in the right half. Set left = mid + 1.
• Narrow Right: Ifarr[mid] > target, the target is in the left half. Set right = mid - 1.
• Repeat: Continue until left > right, which means the target is not in the array.

Let's trace the algorithm searching for value 23 in a sorted array.

Below is the implementation of Binary Search in multiple programming languages. Both iterative and recursive approaches are commonly used.

#include <stdio.h>
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target)
            return mid;  // Element found
        
        if (arr[mid] < target)
            left = mid + 1;  // Search right half
        else
            right = mid - 1;  // Search left half
    }
    
    return -1;  // Element not found
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    
    int result = binarySearch(arr, n, target);
    
    if (result == -1)
        printf("Element not found");
    else
        printf("Element found at index %d", result);
    
    return 0;
}

Binary Search is remarkably efficient, making it a go-to algorithm for searching in sorted collections.

Time Complexity

Space Complexity

Binary Search is the preferred algorithm whenever you are working with sorted data and need fast lookups.