Binary Search: Fundamentals & Boundary Patterns

Binary Search is a foundational divide-and-conquer algorithm designed to efficiently search a sorted array by repeatedly dividing the search interval in half. This note explores essential binary search patterns including lower bound, upper bound, insert positions, floor/ceil calculations, and range boundary searches.

---

1. Lower Bound in a Sorted Array

Problem Description

Given a sorted array nums of N integers and a target value x, find the lower bound of x. The lower bound is defined as the smallest index index such that nums[index] >= x. If no such element exists, return N (the length of the array).

Intuition & Approach

The standard binary search checks if nums[mid] == x. For lower bound:

1. Initialize low = 0, high = len(nums) - 1, and ans = -1.
2. Compute mid = (low + high) // 2.
3. If nums[mid] >= x:
   • mid is a potential candidate for the lower bound, so store ans = mid.
   • Search the left half (high = mid - 1) to check if a smaller index satisfies nums[index] >= x.
4. If nums[mid] < x:
   • nums[mid] is strictly smaller than x, so the lower bound must lie in the right half (low = mid + 1).
5. If ans == -1 at the end (no element >= x), return len(nums).

Example Walkthrough

Input: nums = [3, 5, 8, 15, 19], x = 9

• Iteration 1: low = 0, high = 4 → mid = 2 (nums[2] = 8).
  • 8 < 9, so set low = mid + 1 = 3.
• Iteration 2: low = 3, high = 4 → mid = 3 (nums[3] = 15).
  • 15 >= 9, update ans = 3 and set high = mid - 1 = 2.
• Loop terminates (low > high).

Output: 3 (Index of element 15)

Python Solution

class Solution:
    def lower_bound(self, nums: list, x: int) -> int:
        ans = -1
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == x:
                ans = mid
                high = mid - 1
            elif nums[mid] > x:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1

        return len(nums) if ans == -1 else ans

def main():
    nums = [3, 5, 8, 15, 19]
    x = 9

    sol = Solution()
    print(sol.lower_bound(nums, x))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Search space is halved in every iteration.
• Space Complexity: O(1) — Constant auxiliary space.

---

2. Upper Bound in a Sorted Array

Problem Description

Given a sorted array nums of N integers and a target value x, find the upper bound of x. The upper bound is defined as the smallest index index such that nums[index] > x. If no such element exists, return N.

Intuition & Approach

Upper bound differs slightly from lower bound as it requires a strictly greater element (nums[mid] > x):

1. Maintain low = 0, high = len(nums) - 1, and ans = -1.
2. Compute mid = (low + high) // 2.
3. If nums[mid] > x:
   • mid is a valid candidate, so save ans = mid.
   • Search left (high = mid - 1) for an even smaller valid index.
4. If nums[mid] <= x:
   • nums[mid] is less than or equal to x, so push search to the right (low = mid + 1).
5. If ans remains -1, return len(nums).

Example Walkthrough

Input: nums = [3, 5, 8, 15, 19], x = 2

• Iteration 1: low = 0, high = 4 → mid = 2 (nums[2] = 8).
  • 8 > 2, store ans = 2, move left: high = 1.
• Iteration 2: low = 0, high = 1 → mid = 0 (nums[0] = 3).
  • 3 > 2, update ans = 0, move left: high = -1.
• Loop terminates.

Output: 0 (Index of element 3)

Python Solution

class Solution:
    def upper_bound(self, nums: list, x: int) -> int:
        ans = -1
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] > x:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1

        return len(nums) if ans == -1 else ans

def main():
    nums = [3, 5, 8, 15, 19]
    x = 2

    sol = Solution()
    print(sol.upper_bound(nums, x))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Binary search reduces search space logarithmically.
• Space Complexity: O(1) — In-place index pointers.

---

3. Search Insert Position

Problem Description

Given a sorted array of distinct integers nums and a target value target, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Intuition & Approach

The search insert position is equivalent to finding the lower bound of target:

1. If target exists in the array, return its index immediately when nums[mid] == target.
2. If nums[mid] > target, store ans = mid and move left (high = mid - 1).
3. If nums[mid] < target, move right (low = mid + 1).
4. If target is greater than all elements in the array, ans stays -1, so return len(nums).

Example Walkthrough

Input: nums = [1, 3, 5, 6], target = 2

• Iteration 1: low = 0, high = 3 → mid = 1 (nums[1] = 3).
  • 3 > 2, set ans = 1, search left: high = 0.
• Iteration 2: low = 0, high = 0 → mid = 0 (nums[0] = 1).
  • 1 < 2, search right: low = 1.
• Loop terminates.

Output: 1

Python Solution

class Solution:
    def search_insert(self, nums: list, target: int) -> int:
        ans = -1
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1

        return len(nums) if ans == -1 else ans

def main():
    sol = Solution()
    nums = [1, 3, 5, 6]
    target = 2

    print(sol.search_insert(nums, target))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Logarithmic search time.
• Space Complexity: O(1) — Zero extra allocations.

---

4. Floor and Ceil in a Sorted Array

Problem Description

Given a sorted array nums and an integer x, find the floor and ceil of x in nums:

• Floor: Largest element in nums that is <= x. Return -1 if it doesn't exist.
• Ceil: Smallest element in nums that is >= x. Return -1 if it doesn't exist.

Intuition & Approach

We run two targeted binary searches (or combined tracking):

1. Find Floor:
   • If nums[mid] == x, floor = nums[mid] (exact match found).
   • If nums[mid] < x, nums[mid] is a valid candidate for floor. Update floor = nums[mid] and move right (low = mid + 1) to find a larger potential floor.
   • If nums[mid] > x, move left (high = mid - 1).
2. Find Ceil:
   • If nums[mid] == x, ceil = nums[mid].
   • If nums[mid] > x, nums[mid] is a candidate for ceil. Update ceil = nums[mid] and move left (high = mid - 1) to find a smaller potential ceil.
   • If nums[mid] < x, move right (low = mid + 1).

Example Walkthrough

Input: nums = [3, 4, 4, 7, 8, 10], x = 5

• Floor Search:
  • mid = 2 (nums[2] = 4): 4 < 5 → floor = 4, low = 3.
  • mid = 4 (nums[4] = 8): 8 > 5 → high = 3.
  • mid = 3 (nums[3] = 7): 7 > 5 → high = 2.
  • Result floor = 4.
• Ceil Search:
  • mid = 2 (nums[2] = 4): 4 < 5 → low = 3.
  • mid = 4 (nums[4] = 8): 8 > 5 → ceil = 8, high = 3.
  • mid = 3 (nums[3] = 7): 7 > 5 → ceil = 7, high = 2.
  • Result ceil = 7.

Output: [4, 7]

Python Solution

class Solution:
    def get_floor_and_ceil(self, nums: list, x: int) -> list:
        floor, ceil = [-1, -1]

        # Search for Floor
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == x:
                floor = nums[mid]
                break
            elif nums[mid] < x:
                low = mid + 1
                floor = nums[mid]
            else:
                high = mid - 1

        # Search for Ceil
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == x:
                ceil = nums[mid]
                break
            elif nums[mid] > x:
                ceil = nums[mid]
                high = mid - 1
            else:
                low = mid + 1

        return [floor, ceil]

def main():
    sol = Solution()
    nums = [3, 4, 4, 7, 8, 10]
    x = 5

    print(sol.get_floor_and_ceil(nums, x))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Two independent binary search passes of logarithmic time.
• Space Complexity: O(1) — Constant memory.

---

5. First and Last Occurrence of Element

Problem Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. Return [-1, -1] if target is not found.

Intuition & Approach

When duplicates exist, finding an index equal to target isn't enough. We run two separate binary searches:

1. First Occurrence Search (First Boundary):
   • When nums[mid] == target, record ans[0] = mid, then squeeze left (high = mid - 1) to look for earlier occurrences.
2. Last Occurrence Search (Last Boundary):
   • When nums[mid] == target, record ans[1] = mid, then squeeze right (low = mid + 1) to look for later occurrences.

Example Walkthrough

Input: nums = [5, 7, 7, 8, 8, 10], target = 8

• First occurrence pass:
  • Finds nums[3] = 8 → ans[0] = 3, sets high = 2.
  • Next checks nums[1] and nums[2] (both 7). Loop ends.
• Last occurrence pass:
  • Finds nums[3] = 8 → ans[1] = 3, sets low = 4.
  • Finds nums[4] = 8 → ans[1] = 4, sets low = 5.
  • Next checks nums[5] (10). Loop ends.

Output: [3, 4]

Python Solution

class Solution:
    def search_range(self, nums: list, target: int) -> list:
        low, high = 0, len(nums) - 1
        ans = [-1, -1]

        # Search First Occurrence
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                ans[0] = mid
                high = mid - 1
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1

        # Search Last Occurrence
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                ans[1] = mid
                low = mid + 1
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1

        return ans

def main():
    nums = [5, 7, 7, 8, 8, 10]
    target = 8

    sol = Solution()
    print(sol.search_range(nums, target))

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(log N) — Two binary search passes.
• Space Complexity: O(1) — Fixed size array output.