Binary Search

Binary Search is an efficient algorithm used to find the position of a target element within a sorted array.

Unlike linear search, it reduces the search interval in half at each step, making it much faster for large datasets.

Key Requirements

The array must be sorted (either ascending or descending).
It follows a divide-and-conquer approach.

How Binary Search Works?

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

Set two pointers: low at the beginning and high at the end of the array.
Find the mid index: mid = (low + high) / 2
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.
Repeat the process until the element is found or the search space is exhausted.

Example of Binary Search

Let’s say array = [5, 10, 15, 20, 25, 30, 35] and Target = 25

Step 1:

low = 0, high = 6

mid = (0 + 6) / 2 = 3

arr[3] = 20 Not equal, and 25 > 20 → Search right half

Step 2:

low = 4, high = 6

mid = (4 + 6) / 2 = 5

arr[5] = 30 Not equal, and 25 < 30 → Search left half

Step 3:

low = 4, high = 4

mid = (4 + 4) / 2 = 4

arr[4] = 25 → Found

Time and Space Complexity of Binary Search

Let n be the number of elements in the array.

Time Complexity

Case	Description	Complexity
Best Case	The element is found at the middle on the first try.	O(1)
Average Case	The search space is halved each time.	O(log n)
Worst Case	The element is not present or at the last checked index.	O(log n)

Why O(log n)?

Because each time we divide the search space into two halves, reducing the problem size exponentially.

Space Complexity

Type	Description	Complexity
Iterative	No extra space used, just a few variables.	O(1)
Recursive	Uses call stack for each recursive call (depth log n).	O(log n)

Advantages of Binary Search

Much faster than linear search for large datasets.
Time complexity is logarithmic grows slowly as data increases.
Efficient for static or rarely changing datasets.

Disadvantages of Binary Search

Requires the data to be sorted.
May be less efficient on small datasets compared to linear search.
Recursive implementation uses extra space on the call stack.

When to Use Binary Search

When the data is already sorted.
When you need high-speed lookup in large datasets.
For implementing in systems like
- Dictionary lookups
- Index tables
- Game leaderboards
- Search in file systems

Binary Search in C Programming

Binary Search is a powerful technique to find an element in a sorted array by repeatedly dividing the search interval in half.

The array must be sorted before applying Binary Search.

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;

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

        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1; // Element not found
}

int main() {
    int arr[] = {5, 10, 15, 20, 25, 30, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 25;

    int result = binarySearch(arr, n, 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 25 found at index 4

Binary Search is a powerful and efficient search algorithm when working with sorted data. While it's not as simple as linear search, its performance benefits are huge especially with large datasets.

Menu