Binary Search Pattern Guide for LeetCode

1. Core Binary Search Templates

Template 1: Basic Binary Search

def binarySearch(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:# Note: <= because we want to include right
        mid = left + (right - left) // 2# Prevent overflow

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1# Not found

Template 2: First Occurrence

def firstOccurrence(nums, target):
    left, right = 0, len(nums) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            result = mid# Found but keep searching left
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Template 3: Last Occurrence

def lastOccurrence(nums, target):
    left, right = 0, len(nums) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            result = mid# Found but keep searching right
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

2. LeetCode Problem Categories

Category 1: Direct Binary Search

1. LeetCode 704: Binary Search

   • Find target in sorted array
   • Use basic template

2. LeetCode 34: Find First and Last Position

   • Find range of target in sorted array
   • Use first/last occurrence templates

3. LeetCode 35: Search Insert Position

   • Find insertion position in sorted array

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

Category 2: Rotated Array Problems

1. LeetCode 33: Search in Rotated Sorted Array

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

# Check which half is sorted
        if nums[left] <= nums[mid]:# Left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:# Right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

1. LeetCode 153: Find Minimum in Rotated Sorted Array
2. LeetCode 154: Find Minimum in Rotated Sorted Array II (with duplicates)