In its simplest form, binary search works on a contiguous sequence with specified left and right indices, also known as the search space.
It continuously narrows down the search range to eventually locate the target value or determine that it does not exist.

---

Basic Concept

• Binary search maintains three pointers: left, right, and mid
• At each step, compare the middle element with the target or condition
• Based on the result, eliminate half of the search space
• Repeat until the target is found or the search space is empty

If the final search space is empty, the target does not exist.

---

🔍 When Should You Use Binary Search?

Checklist:

• Are you searching in a sorted array?
• Are you looking for an index, element, or a position that satisfies a condition?

If the data is unsorted, you can sort it first before applying binary search.

---

🧩 Three Phases of Binary Search

1. Preprocessing: If the collection is unsorted, sort it first
2. Search Process: Use a loop or recursion to narrow the search range
3. Postprocessing: Some templates require checking the remaining element(s) for the condition

---

🔧 Template #1 – Basic Search

The most common binary search, used to check whether a target element exists.

Code Example (Python)

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

✅ Features

• Search space is a closed interval [left, right]
• Loop condition is left <= right
• Each step directly checks for the target
• No postprocessing needed

🔧 Syntax Tips

• Init: left = 0, right = len(nums) - 1
• Move left: right = mid - 1
• Move right: left = mid + 1

📌 Use Cases

• Check if an element exists
• Does not require finding the first or last occurrence

---

🧠 Template #2 – Left Boundary Search

Used to find the smallest/largest value that satisfies a condition, such as lower_bound.

Code Example (Python)

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    if left != len(nums) and nums[left] == target:
        return left
    return -1

✅ Features

• Search space is left-closed, right-open [left, right)
• Loop condition is left < right
• Requires postprocessing: check if nums[left] is the target

🔧 Syntax Tips

• Init: left = 0, right = len(nums)
• Move left: right = mid
• Move right: left = mid + 1

📌 Use Cases

• Find the leftmost element satisfying a condition
• Precise boundary location (e.g., lower_bound)

---

🧲 Template #3 – Neighbor Comparison Method

Used when you need to access both left and right neighbors, such as finding a “peak” or handling specific structures.

Code Example (Python)

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid
        else:
            right = mid

    if nums[left] == target:
        return left
    if nums[right] == target:
        return right
    return -1

✅ Features

• Guarantees at least three elements in the search space
• Termination condition is left + 1 == right
• Requires postprocessing: check nums[left] and nums[right]

🔧 Syntax Tips

• Init: left = 0, right = len(nums) - 1
• Move left: right = mid
• Move right: left = mid

📌 Use Cases

• Peak element problems
• Comparing current element with neighbors

---

🆚 Template Comparison Summary

Feature	Template 1	Template 2	Template 3
Interval definition	[left, right]	[left, right)	[left, right]
Termination condition	left > right	left == right	left + 1 == right
Postprocessing	❌ No	✅ Yes	✅ Yes
Use Case	Existence check	Boundary finding	Neighbor-based problems

---

🎯 Example Comparison

Array: nums = [1, 2, 2, 2, 3], Target: target = 2

Template	Returned Index	Explanation
Template 1	2	Any matching value is fine
Template 2	1	The leftmost 2
Template 3	1 or 2	Depends on neighbor check logic

---

✅ Summary & Recommendation

Goal	Recommended Template
Just check if exists	Template 1
Find boundaries (first/last)	Template 2
Peak or neighbor logic	Template 3