Binary Search

Binary Search is an extremely efficient searching algorithm that finds the position of a target key within a sorted array.

Unlike Linear Search, which eliminates one element at a time, Binary Search eliminates half of the remaining elements in every step. This is the same technique you intuitively use when looking up a word in a physical dictionary you open it in the middle, decide if your word comes before or after that page, and repeat.

The Golden Rules of Binary Search

1. The data structure must be sorted (usually in ascending order).
2. It requires random access to elements (i.e., it works perfectly on arrays but is useless on linked lists).

How Binary Search Works?

Let’s say you want to find a number in a sorted array.

1. Set two pointers: low at the beginning and high at the end of the array.
2. Find the mid index: mid = (low + high) / 2
3. Compare the middle element with the target:
   • If it matches, return the index.
   • If the target is less than arr[mid], search the left half.
   • If the target is greater, search the right half.
4. Repeat the process until the element is found or the search space is exhausted.

Example of Binary Search

Let’s take the sorted array: arr = [2, 3, 5, 6, 7, 8, 9]. We want to search for Key = 7.

We maintain three pointers: low (start of the search space), high (end of the search space), and mid (the middle).

We will trace the algorithm step by step:

• Step 1: Initialize low = 0, high = 6 (size-1). Calculate mid = (0 + 6) / 2 = 3.
  • Compare arr[3] (which is 6) with 7.
  • Since 6 < 7, we know the key must be in the right half. Discard the left half.
  • Update low = mid + 1 = 4.
• Step 2: Now low = 4, high = 6. Calculate mid = (4 + 6) / 2 = 5.
  • Compare arr[5] (which is 8) with 7.
  • Since 8 > 7, the key must be in the left half. Discard the right half.
  • Update high = mid - 1 = 4.
• Step 3: Now low = 4, high = 4. Calculate mid = (4 + 4) / 2 = 4.
  • Compare arr[4] (which is 7) with 7.
  • Match Found! Return index 4.

What if the key is not in the array?

If we searched for Key = 4, the algorithm would eventually make low greater than high (e.g., low = 2, high = 1). At that exact moment, the loop stops, and we return -1.

Algorithm for Binary Search

Algorithm: BinarySearch(arr, low, high, key)
Input:  arr[] - Sorted array
        low - Starting index (usually 0)
        high - Ending index (usually n-1)
        key - The element to find
Output: Index of the key if found, otherwise -1

Step 1: START
Step 2: WHILE low <= high DO
Step 3:     mid = (low + high) / 2
Step 4:     IF arr[mid] == key THEN
Step 5:         RETURN mid   [Successful Search]
Step 6:     ELSE IF arr[mid] < key THEN
Step 7:         low = mid + 1   [Search right half]
Step 8:     ELSE
Step 9:         high = mid - 1  [Search left half]
Step 10: RETURN -1              [Unsuccessful Search]
Step 11: END

Implementation in C Programming

Here is the complete C program The array must be sorted before calling this function.

#include <stdio.h>

// Iterative Binary Search function
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        // Calculate the middle index
        int mid = (low + high) / 2;

        // Check if the key is present at mid
        if (arr[mid] == key) {
            return mid;
        }

        // If the key is greater, ignore the left half
        if (arr[mid] < key) {
            low = mid + 1;
        } 
        // If the key is smaller, ignore the right half
        else {
            high = mid - 1;
        }
    }
    // If we exit the loop, the key was not found
    return -1;
}

int main() {
    // Important: The array MUST be sorted for binary search
    int arr[] = {2, 3, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int result = binarySearch(arr, 0, n - 1, key);

    if (result != -1) {
        printf("Element %d found at index %d.\n", key, result);
    } else {
        printf("Element %d not found in the array.\n", key);
    }
    return 0;
}

Output:

Element 7 found at index 4.

Time and Space Complexity Analysis

Time Complexity

At each step, we divide the search space exactly in half. If n is the number of elements, the maximum number of steps required is log₂(n).

Why is it O(log n)?

If n = 1,000,000, Binary Search takes at most 20 steps (since 2^20 ≈ 1 million) to find the element. Compared to Linear Search, which would take 1,000,000 steps, this is exponentially faster.

Space Complexity

• Iterative Version: O(1) constant space.
• Recursive Version: O(log n) due to the call stack memory.

Advantages of Binary Search

1. Incredibly Fast: Logarithmic time complexity makes it ideal for large datasets.
2. Minimal Comparisons: It drastically reduces the number of comparisons compared to Linear Search.
3. Low Memory Overhead (Iterative): It doesn't consume extra memory for the search process.

Disadvantages of Binary Search

1. Requires Sorted Data: The data must be pre-sorted. Sorting itself costs O(n log n) if the data is unsorted.
2. Static Data Only: Insertion and deletion in a sorted array are expensive (O(n) to shift elements).
3. Poor with Linked Lists: It heavily relies on random access (arr[mid]). In a linked list, finding the middle takes O(n), defeating the purpose.

When to Use Binary Search?

• When the dataset is large and static (you don't frequently insert/delete).
• When the array is already sorted.
• When you need a guaranteed logarithmic time performance.
• When you have random access memory (arrays).

Real-World Analogy

Imagine you are looking for a specific phone number in a 1000-page telephone directory. You do not start at page 1 and read every name. Instead, you open the book to the middle, check if your name's letter comes before or after that page, and repeat. 

That is precisely Binary Search eliminating half the remaining possibilities with each step.