Binary Search Basics

🔍 What is Binary Search?

Binary Search is a fast algorithm to search for an element in a sorted array (or range). It repeatedly divides the search space in half, eliminating one half at a time.

---

🧠 When to Use Binary Search?

Use Binary Search when:

✅ The array or list is sorted (ascending or descending)
✅ You want to search quickly (better than linear time)
✅ You're trying to minimize or maximize something (like minimum largest sum, peak element, etc.)

---

⚙️ How Does It Work?

Imagine:

You have a sorted list:
nums = [1, 3, 5, 7, 9, 11, 13]
And you're searching for 9.

Steps:

1. Set two pointers:
   left = 0, right = nums.size() - 1

2. Calculate the middle:
   mid = (left + right) / 2

3. Compare nums[mid] with target:

   • If equal: 🎯 Found it!

   • If nums[mid] < target: Search in right half → left = mid + 1

   • If nums[mid] > target: Search in left half → right = mid - 1

Repeat this loop until left > right.

---

🔄 What’s Happening Internally?

Step	Left	Right	Mid	nums[Mid]	Action
1	0	6	3	7	7 < 9 → Search right
2	4	6	5	11	11 > 9 → Search left
3	4	4	4	9	🎯 Found target

---

🧮 Time and Space Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1) if done iteratively; O(log n) for recursion

---

🛠️ C++ Template Code

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // to avoid overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1; // not found
}

---

📦 Use Cases

• Finding a number in a sorted array

• Finding first or last occurrence (modified binary search)

• Solving optimization problems (e.g., minimum days, max sweetness)

• Search space problems where answer lies in a range, not an index

Binary search is an efficient algorithm to find an element in a sorted array.
Time Complexity: O(log n)
Brute-force alternative: Linear search → O(n)

🔧 C++ Binary Search Syntax

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 4, 4, 5, 6, 8, 10};
    int x = 4;

    // 1. binary_search
    bool exists = binary_search(arr.begin(), arr.end(), x);
    cout << "Exists? " << exists << endl;

    // 2. lower_bound
    auto lb = lower_bound(arr.begin(), arr.end(), x);
    cout << "Lower bound of 4: index " << (lb - arr.begin()) << endl;

    // 3. upper_bound
    auto ub = upper_bound(arr.begin(), arr.end(), x);
    cout << "Upper bound of 4: index " << (ub - arr.begin()) << endl;

    return 0;
}

---

🧪 2. Input/Output with Iteration Tables

Given:

arr = {1, 2, 4, 4, 5, 6, 8, 10}
x = 4

✅ Output:

Function	Result	Description
binary_search	true	4 exists
lower_bound	index 2	first index where arr[i] >= 4
upper_bound	index 4	first index where arr[i] > 4

---

📈 3. Binary Search Iteration Table Example

Searching for 4 in {1, 2, 4, 4, 5, 6, 8, 10}

Iteration	low	mid	high	arr[mid]	Action
1	0	3	7	4	Found 4!

Very few steps even in large arrays due to halving.

---

⚙️ 4. Brute Force vs Binary Search (Performance)

Method	Time Complexity	Description
Brute-force	O(n)	Iterate through every element
Binary search	O(log n)	Divide array each iteration

For n = 1e6, brute-force takes ~1 million steps, binary search takes ~20.

---

📘 5. LeetCode Problems Using Binary Search

✅ Easy:

• 704. Binary Search

• 35. Search Insert Position

• 278. First Bad Version

✅ Medium:

• 33. Search in Rotated Sorted Array

• 162. Find Peak Element

• 153. Find Minimum in Rotated Sorted Array

• 34. Find First and Last Position of Element in Sorted Array

✅ Hard:

• 410. Split Array Largest Sum (min/max via BS)

• 1231. Divide Chocolate

---

🔎 6. Min/Max Binary Search (Search Space Binary Search)

Used when you need to minimize/maximize a result.

📌 Problem Example:

875. Koko Eating Bananas

Find the minimum speed k to eat all bananas in h hours.

int minEatingSpeed(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = (low + high) / 2;
        int hours = 0;
        for (int pile : piles)
            hours += (pile + mid - 1) / mid;
        if (hours > h)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

🧠 You binary search on speed, not index!

---

⚖️ 7. lower_bound() vs upper_bound()

Example:

vector<int> v = {1, 2, 4, 4, 5};

lower_bound(v.begin(), v.end(), 4); // returns iterator to first 4 (index 2)
upper_bound(v.begin(), v.end(), 4); // returns iterator to first element > 4 (index 4)

---

✅ When to Use Which Mechanism?

Problem Type	Use
Find element in sorted array	binary_search
First occurrence (≥ x)	lower_bound
First greater (> x)	upper_bound
Find min/max value satisfying a condition	Custom binary search on range