Binary Search

How it works

Lower bound binary search finds the first index where a value is greater than or equal to the target.
This means if the target exists in the array, this lower-bound index will point exactly to its first occurrence.
So instead of directly searching for equality, we search for the leftmost position where the target could appear, then verify it.

This approach is especially useful for sorted arrays because it avoids overshooting and naturally handles duplicates.

Steps

1. Initialize:
   • l = 0
   • r = len(nums) (right is one past the last index).
2. While l < r:
   • Compute midpoint m.
   • If nums[m] >= target, shrink the search to the left half: r = m.
   • Otherwise (nums[m] < target), search in the right half: l = m + 1.
3. After the loop:
   • l is the lower bound: first index where value >= target.
4. If l is within bounds and nums[l] == target, return l.
5. Otherwise, return -1 (the target is not in the array).

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Integer Overflow When Calculating Mid

Using (l + r) / 2 can overflow when l and r are large. Use l + (r - l) / 2 instead to safely compute the midpoint.

Infinite Loop Due to Wrong Pointer Update

Updating l = m instead of l = m + 1 (or r = m instead of r = m - 1 in some variants) can cause an infinite loop when l and r are adjacent.

Off-by-One Errors with Loop Condition

Using while l <= r vs while l < r changes the behavior significantly. Mixing these up with the wrong pointer updates causes bugs. Be consistent with your chosen template.

Not Checking if Target Was Actually Found

Binary search converges to a position, but that position might not contain the target. Always verify that nums[result] == target before returning the index.

from typing import List

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

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l if (l < len(nums) and nums[l] == target) else -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l < nums.size() && nums[l] == target) ? l : -1;
    }
};