Binary Search in Data Structures

1️⃣ What is Binary Search?

🔹 Binary Search is an efficient searching algorithm used for sorted data.
🔹 It follows a divide-and-conquer approach by repeatedly dividing the search space in half.
🔹 Time Complexity:

• Best Case: O(1) (if the middle element is the target).
• Worst Case: O(log n) (reduces search space by half in each step).
  🔹 Best for: Large datasets that are sorted.

---

2️⃣ How Binary Search Works

Steps:

1️⃣ Find the middle element of the array.
2️⃣ If the middle element matches the key, return its position.
3️⃣ If the key is smaller than the middle element, search in the left half.
4️⃣ If the key is greater than the middle element, search in the right half.
5️⃣ Repeat the process until the element is found or the search space is empty.

---

3️⃣ Binary Search Implementation in C

✅ Iterative Approach

#include <stdio.h>

// Function to perform Binary Search
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) return mid;  // Element found

        if (arr[mid] < key) left = mid + 1;  // Search right half
        else right = mid - 1;  // Search left half
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};  // Sorted array
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    int index = binarySearch(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Iterative approach avoids extra memory usage from recursion.
❌ More complex than linear search but much faster for large datasets.

---

✅ Recursive Approach

#include <stdio.h>

// Recursive Binary Search Function
int binarySearchRecursive(int arr[], int left, int right, int key) {
    if (left > right) return -1;  // Base case: Not found

    int mid = left + (right - left) / 2;

    if (arr[mid] == key) return mid;  // Element found

    if (arr[mid] < key)  // Search right half
        return binarySearchRecursive(arr, mid + 1, right, key);

    return binarySearchRecursive(arr, left, mid - 1, key);  // Search left half
}

int main() {
    int arr[] = {2, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 8;

    int index = binarySearchRecursive(arr, 0, n - 1, key);
    if (index != -1)
        printf("Element found at index %d\n", index);
    else
        printf("Element not found\n");

    return 0;
}

✅ Recursive approach is easier to understand.
❌ Uses extra function calls (stack memory).

---

4️⃣ Comparison: Iterative vs Recursive Binary Search

Feature	Iterative Binary Search	Recursive Binary Search
Memory Usage	Uses a single loop (O(1) space)	Uses recursion stack (O(log n) space)
Performance	Faster (no recursive calls)	Slightly slower due to function calls
Ease of Understanding	Complex logic but efficient	More intuitive but costly in memory
Use Case	Large datasets, performance-critical apps	When simplicity is preferred

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Much faster than Linear Search (O(log n) vs. O(n))
✔ Works well for large datasets
✔ Efficient memory usage (Iterative approach: O(1) extra space)

❌ Disadvantages

❌ Only works on sorted arrays
❌ Requires additional steps to maintain a sorted dataset
❌ Recursive approach can lead to stack overflow for very large inputs