Binary Search Algorithm

Binary Search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, making it much faster than linear search for large datasets.

How Binary Search Works

Binary Search works by comparing the target value to the middle element of the array:

1. If the target value equals the middle element, the search is successful.
2. If the target value is less than the middle element, search the left half of the array.
3. If the target value is greater than the middle element, search the right half of the array.
4. Repeat this process until the value is found or the search interval is empty.

Visual Representation

Binary Search Implementation

Below are implementations of the Binary Search algorithm in multiple programming languages:

1#include <stdio.h>
2
3// Iterative Binary Search
4int binarySearch(int arr[], int n, int target) {
5    int left = 0;
6    int right = n - 1;
7    
8    while (left <= right) {
9        int mid = left + (right - left) / 2;
10        
11        // Check if target is present at mid
12        if (arr[mid] == target)
13            return mid;
14        
15        // If target is greater, ignore left half
16        if (arr[mid] < target)
17            left = mid + 1;
18        
19        // If target is smaller, ignore right half
20        else
21            right = mid - 1;
22    }
23    
24    // Element not present in array
25    return -1;
26}
27
28// Recursive Binary Search
29int binarySearchRecursive(int arr[], int left, int right, int target) {
30    if (right >= left) {
31        int mid = left + (right - left) / 2;
32        
33        // If the element is present at the middle
34        if (arr[mid] == target)
35            return mid;
36        
37        // If element is smaller than mid, search in left subarray
38        if (arr[mid] > target)
39            return binarySearchRecursive(arr, left, mid - 1, target);
40        
41        // Else search in right subarray
42        return binarySearchRecursive(arr, mid + 1, right, target);
43    }
44    
45    // Element not present in array
46    return -1;
47}
48
49int main() {
50    int arr[] = {2, 3, 4, 10, 40, 50, 70, 85};
51    int n = sizeof(arr) / sizeof(arr[0]);
52    int target = 10;
53    
54    int result = binarySearch(arr, n, target);
55    if (result == -1)
56        printf("Element %d not present in array\n", target);
57    else
58        printf("Element %d found at index %d\n", target, result);
59    
60    result = binarySearchRecursive(arr, 0, n - 1, target);
61    if (result == -1)
62        printf("Element %d not present in array (recursive)\n", target);
63    else
64        printf("Element %d found at index %d (recursive)\n", target, result);
65    
66    return 0;
67}

Time and Space Complexity

Time Complexity Analysis

• Best Case: O(1) when the target element is at the middle of the array and found in the first comparison.
• Average Case: O(log n) as we eliminate half of the remaining elements in each step.
• Worst Case: O(log n) even when the element is not in the array or is at the beginning/end.

Space Complexity Analysis

The iterative implementation of Binary Search has a space complexity of O(1) as it only uses a constant amount of extra space. The recursive implementation has a space complexity of O(log n) due to the call stack.

Advantages and Disadvantages

Common Applications

Binary Search is used in many real-world applications:

• Database Systems: For searching through sorted indices.
• Dictionary Lookups: Finding words in a sorted dictionary.
• Debugging: Binary search debugging (bisect) to find bugs in code.
• Computer Graphics: For intersection detection in ray tracing.
• Machine Learning: In algorithms like binary decision trees.

Variations of Binary Search

Several variations of the Binary Search algorithm exist for different scenarios:

Practice Problems

To solidify your understanding of Binary Search, try these practice problems:

Related Searching Algorithms

If you're interested in learning more about searching algorithms, here are some related algorithms to explore:

• Linear Search - Simple search algorithm with O(n) time complexity
• Depth-First Search - Graph traversal algorithm that explores as far as possible along each branch
• Breadth-First Search - Graph traversal algorithm that explores all neighbors at the present depth
• Interpolation Search - Improved variant of binary search for uniformly distributed data