🔍 Binary Search – Efficient Searching Algorithm

**Binary Search** is a **divide-and-conquer algorithm** used to find an element in a **sorted array** efficiently. It **reduces the search space by half** at each step, making it significantly faster than **linear search**.

📌 Key Properties of Binary Search

  • ✅ Works on **sorted data only**.
  • ✅ Reduces search space **by half** each time (**O(log n) complexity**).
  • ✅ Can be implemented **iteratively** or **recursively**.
  • ❌ Cannot be used for **unsorted arrays**.

⚙️ How Does Binary Search Work?

🔢 **Step-by-Step Explanation**

  1. ✅ **Find the middle element** of the array.
  2. 🔎 **Compare** the middle element with the target value:
    • 🎯 If **equal**, return the index.
    • ⬅️ If **smaller**, search in the **left half**.
    • ➡️ If **greater**, search in the **right half**.
  3. 🔄 Repeat the process **until the element is found** or search space is **empty**.

📌 Example – Searching for 7 in a Sorted Array

**Array:** [1, 3, 5, 7, 9, 11, 15]

Step Search Space Middle Element Action
1 [1, 3, 5, 7, 9, 11, 15] 7 🎯 Found! Return index 3.

🛠️ Binary Search Implementation

🔄 Iterative Binary Search (C++)


                int binarySearch(int arr[], int left, int right, int target) {
                    while (left <= right) {
                        int mid = left + (right - left) / 2;
                        if (arr[mid] == target) return mid;
                        else if (arr[mid] < target) left = mid + 1;
                        else right = mid - 1;
                    }
                    return -1; // Not found
                }

🔁 Recursive Binary Search (C++)


                int recursiveBinarySearch(int arr[], int left, int right, int target) {
                    if (left > right) return -1; // Not found
                    int mid = left + (right - left) / 2;
                    if (arr[mid] == target) return mid;
                    else if (arr[mid] < target) return recursiveBinarySearch(arr, mid + 1, right, target);
                    else return recursiveBinarySearch(arr, left, mid - 1, target);
                }

⚖️ Binary Search vs Linear Search

Feature Binary Search Linear Search
Time Complexity O(log n) O(n)
Best Case O(1) (Middle element found) O(1) (First element is target)
Worst Case O(log n) O(n)
Use Case Sorted Arrays Unsorted & Small Arrays

⏳ Time Complexity Analysis

  • ✅ **Best Case:** O(1) → Found at the middle.
  • ⚡ **Average Case:** O(log n) → Divides the array into halves.
  • ❌ **Worst Case:** O(log n) → Element not found after **log n** steps.

📌 Variations of Binary Search

🔄 **1. Lower Bound Binary Search**

Finds the **smallest index** where the value is **greater than or equal** to the target.


                int lowerBound(int arr[], int n, int target) {
                    int left = 0, right = n;
                    while (left < right) {
                        int mid = left + (right - left) / 2;
                        if (arr[mid] >= target) right = mid;
                        else left = mid + 1;
                    }
                    return left;
                }

🔼 **2. Upper Bound Binary Search**

Finds the **smallest index** where the value is **strictly greater** than the target.


                int upperBound(int arr[], int n, int target) {
                    int left = 0, right = n;
                    while (left < right) {
                        int mid = left + (right - left) / 2;
                        if (arr[mid] > target) right = mid;
                        else left = mid + 1;
                    }
                    return left;
                }

🌍 Real-World Applications of Binary Search

  • 🔎 **Search Engines** – Fast document retrieval.
  • 📂 **Databases & Indexing** – Binary search trees & B-Trees.
  • 🛒 **E-commerce** – Price filtering & range-based searches.
  • 📡 **Network Routing** – Optimized IP lookup in network tables.
  • 📉 **Stock Market Analysis** – Predicting stock values.

🔗 Next Topics