Here is the solutions for Binary Search.

1. Understand the problem

• Binary Search is used to efficiently find an element’s position in a sorted array.

• Instead of scanning every element (like linear search), it repeatedly divides the search space by half.

2. Clarify constraints (ask 4–5 questions)

1. Is the array sorted? If so, ascending or descending?

2. Can there be duplicate values, and if found, do we return any index or the first/last occurrence?

3. What should we return if the target is not in the array?

4. What is the size range of the input array?

5. Can the array be empty?

3. Explore examples

4. Brainstorm 2 - 3 solutions

4.1. Solution 1: Naive (Linear Search) - O(N)

• Check every element one by one.

• Time: O(N)

• Space: O(1)

👉 Useful only for unsorted arrays.

4.2. Solution 2: Binary Search (Iterative) - O(logN)

• Use two pointers left and right, repeatedly shrink range.

• Time: O(log N)

• Space: O(1)

=> Works only if the array is sorted.

4.3. Solution 3: Binary Search (Recursive) - O(logN)

• Same idea, using recursion.

• Time: O(log N)

• Space: O(log N) (due to recursion stack)

5. Implement solutions

5.1. Recursive Binary Search - O(logN) - 1 value

• Using divide and conquer to search for item.

class Solution:
    def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
        if l > r:
            return -1
        m = l + (r - l) // 2

        if nums[m] == target:
            return m
        if nums[m] < target:
            return self.binary_search(m + 1, r, nums, target)
        return self.binary_search(l, m - 1, nums, target)

    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(0, len(nums) - 1, nums, target)

• Time: O(logN).

• Space: O(logN).

5.2. Iterative Binary Search - O(logN) - 1 value

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            # (l + r) // 2 can lead to overflow
            m = l + ((r - l) // 2)

            if nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                return m
        return -1

• Time: O(logN).

• Space: O(1).

Note: (l + r) can lead to overflow, but r - l is too much smaller.

5.3. Upperbound Binary Search - O(logN) - N values → First index where value > target

1. Normal Binary Search: stops when l > r.

2. Upper Bound Binary Search: stops when l == r.

Idea:

• Instead of stopping when we find target, we push as far right as possible until we reach the point where elements become greater than target.

• So the last value greater than target is l => value is l - 1.

• For normal binary search: When nums[m] > target 👉 We know mid is definitely not the answer, so we remove mid from the search range.

• For Upper Bound Binary Search: So when nums[m] > target => 👉 m might be the first element that is greater (we can’t rule out mid yet) => Because we find the first element larger than target.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)

        # [l, r)
        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] > target:
                r = m # move to the left
            elif nums[m] <= target:
                l = m + 1  # move to right
        return l - 1 if (l and nums[l - 1] == target) else -1

• Time: O(logN).

• Space: O(1).

5.4. Lowerbound Binary Search - O(logN) - N values → First index where value ≥ target

• Find the first index where nums[index] == target (or equivalently, the first element that is ≥ target)

🔍 Two Styles of Binary Search

1️⃣ Traditional (Exact Match)

👉 Uses closed interval → [left, right] 📌 Includes both left and right as valid search positions.

left = 0
right = len(nums) - 1
while left <= right:

2️⃣ Lower/Upper Bound style

👉 Uses half-open interval → [left, right) 📌 Includes left, excludes right

left = 0
right = len(nums)
while left < right:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)

        # [l, r)
        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m # move to the left
            elif nums[m] < target:
                l = m + 1 # move to right
        return l if (l < len(nums) and nums[l] == target) else -1

• Time: O(logN).

• Space: O(1).

5.5. Intuitions

🧠 LOWER BOUND – “first index where value is ≥ target” (đẩy con right về)

🔼 UPPER BOUND – “first index where value is > target” (đẩy con left reach the max)

5.6. Built-In Function

import bisect
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)
        return index if index < len(nums) and nums[index] == target else -1

• Time: O(logN).

• Space: O(1).