Binary Search - Complete Guide

Learn, Visualize, and Understand Binary Search Algorithm

What is Binary Search?

Binary Search is a highly efficient searching algorithm that works exclusively on sorted arrays. Unlike linear search which checks each element one by one, binary search divides the search space in half with each comparison, making it exponentially faster.

Key Characteristics

  • Requirement: Array must be sorted (ascending or descending)
  • Strategy: Divide and conquer approach
  • Efficiency: Eliminates half of remaining elements in each step
  • Time Complexity: O(log n) - Much faster than O(n) linear search

Real-Life Example

Dictionary Search: Imagine you're looking for the word "python" in a dictionary.

  1. Open the dictionary in the middle
  2. Check if "python" comes before or after the middle word
  3. If it comes after, ignore the first half and repeat with the second half
  4. Continue this process until you find "python"

This is exactly how binary search works!

How Binary Search Works

Step 1: Start with three pointers: low (start), high (end), and mid (middle)

Step 2: Calculate middle index: mid = (low + high) / 2

Step 3: Compare the target with middle element:

  • If arr[mid] == target → Found! Return index
  • If arr[mid] < target → Search right half (set low = mid + 1)
  • If arr[mid] > target → Search left half (set high = mid - 1)

Step 4: Repeat until element is found or low > high

Complexity Analysis

Case Time Complexity Description
Best Case O(1) Element found at middle in first comparison
Average Case O(log n) Element found after multiple divisions
Worst Case O(log n) Element at end or not present
Space Complexity O(1) Iterative approach (O(log n) for recursive)

Advantages

  • ✅ Extremely fast for large datasets
  • ✅ Reduces search operations exponentially
  • ✅ Efficient memory usage
  • ✅ Simple to implement

Disadvantages

  • ❌ Requires sorted array (sorting overhead)
  • ❌ Not suitable for linked lists (no random access)
  • ❌ Overkill for small datasets

Interactive Binary Search Visualization

Watch how binary search algorithm finds elements step-by-step with visual animations

Normal
Active Range
Checking
Found
Eliminated

Binary Search - C Code Implementation

See the C code and watch how it executes step-by-step

C Source Code

1#include <stdio.h>
2
3int binarySearch(int arr[], int n, int target) {
4 int low = 0;
5 int high = n - 1;
6
7 while (low <= high) {
8 int mid = low + (high - low) / 2;
9
10 if (arr[mid] == target) {
11 return mid;
12 }
13 else if (arr[mid] < target) {
14 low = mid + 1;
15 }
16 else {
17 high = mid - 1;
18 }
19 }
20 return -1;
21}

Variables

arr[] -
n -
target -
low -
mid -
high -
arr[mid] -

Console Output

Ready to execute. Click "Execute Code" to start.

C Code

#include <stdio.h>

// Binary Search Function - Returns index of target element
int binarySearch(int arr[], int n, int target) {
    int low = 0;              // Start of search range
    int high = n - 1;         // End of search range
    
    // Continue while valid search space exists
    while (low <= high) {
        // Calculate middle index (avoids overflow)
        int mid = low + (high - low) / 2;
        
        printf("Step: low=%d, mid=%d, high=%d | arr[%d]=%d\\n", 
               low, mid, high, mid, arr[mid]);
        
        // Check if target is at middle
        if (arr[mid] == target) {
            return mid;       // Found! Return index
        }
        
        // If target is greater, search right half
        else if (arr[mid] < target) {
            low = mid + 1;
            printf("Target greater. Search right half.\\n\\n");
        }
        
        // If target is smaller, search left half
        else {
            high = mid - 1;
            printf("Target smaller. Search left half.\\n\\n");
        }
    }
    
    return -1;  // Target not found
}

int main() {
    int arr[] = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 25;
    
    printf("Array: ");
    for(int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\nSearching for: %d\\n\\n", target);
    
    int result = binarySearch(arr, n, target);
    
    if (result != -1) {
        printf("\\n✓ Element %d found at index %d\\n", target, result);
    } else {
        printf("\\n✗ Element %d not found\\n", target);
    }
    
    return 0;
}