1. Define a search space [left, right]
2. Define a condition: does this value satisfy the requirement?
3. Narrow the space: if condition met → search left half (or right half)
4. Repeat until the space collapses to a single answer

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1                        # Track best (leftmost) match found so far

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

        if arr[mid] == target:
            result = mid               # Record this match
            right = mid - 1           # Keep searching LEFT for an earlier match
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

# --- Example ---
arr = [2, 4, 4, 4, 7, 9, 9, 11]
print(find_first(arr, 4))   # Output: 1  (first 4 is at index 1)
print(find_first(arr, 9))   # Output: 5  (first 9 is at index 5)

1
5

def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

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

        if arr[mid] == target:
            result = mid               # Record this match
            left = mid + 1            # Keep searching RIGHT for a later match
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

# --- Example ---
arr = [2, 4, 4, 4, 7, 9, 9, 11]
print(find_last(arr, 4))    # Output: 3  (last 4 is at index 3)
print(find_last(arr, 9))    # Output: 6  (last 9 is at index 6)

3
6

import bisect

# bisect_left: find leftmost position to insert target
# bisect_right: find rightmost position to insert target

arr = [10, 20, 30, 40, 50]

print(bisect.bisect_left(arr, 30))    # Output: 2  (before existing 30)
print(bisect.bisect_right(arr, 30))   # Output: 3  (after existing 30)
print(bisect.bisect_left(arr, 25))    # Output: 2  (between 20 and 30)

2
3
2

import bisect

scores = [10, 20, 30, 40, 50, 60, 70, 80, 90]
grade_boundaries = [60, 70, 80, 90, 100]
grades = ['F', 'D', 'C', 'B', 'A']

def get_grade(score):
    # bisect_left finds where score fits in grade_boundaries
    # That index maps directly to the grades list
    return grades[bisect.bisect_left(grade_boundaries, score)]

for score in [55, 65, 75, 85, 95]:
    print(f"Score {score}: {get_grade(score)}")

Score 55: F
Score 65: D
Score 75: C
Score 85: B
Score 95: A

Original: [0, 1, 2, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 0, 1, 2]
                      ^--- rotation point

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

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

        if arr[mid] == target:
            return mid

        # Determine which half is sorted
        if arr[left] <= arr[mid]:             # LEFT half is sorted
            if arr[left] <= target < arr[mid]: # Target is in left half
                right = mid - 1
            else:                              # Target is in right half
                left = mid + 1
        else:                                  # RIGHT half is sorted
            if arr[mid] < target <= arr[right]: # Target is in right half
                left = mid + 1
            else:                               # Target is in left half
                right = mid - 1

    return -1

# --- Example ---
arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0))   # Output: 4
print(search_rotated(arr, 3))   # Output: -1

4
-1

def find_peak(arr):
    left, right = 0, len(arr) - 1

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

        if arr[mid] > arr[mid + 1]:   # Descending — peak is in LEFT half
            right = mid               # (mid itself could be the peak)
        else:                         # Ascending — peak is in RIGHT half
            left = mid + 1

    return left                       # left == right, this is the peak index

# --- Example ---
arr = [1, 3, 20, 4, 1, 0]
peak_idx = find_peak(arr)
print(f"Peak is {arr[peak_idx]} at index {peak_idx}")  # Output: Peak is 20 at index 2

Peak is 20 at index 2

def can_ship(weights, capacity, days):
    """Check if all packages can be shipped in `days` days with given capacity."""
    current_load = 0
    days_used = 1
    for w in weights:
        if current_load + w > capacity:
            days_used += 1
            current_load = 0
        current_load += w
    return days_used <= days

def min_ship_capacity(weights, days):
    left = max(weights)          # Minimum: must fit heaviest package
    right = sum(weights)         # Maximum: ship everything in one day

    while left < right:
        mid = left + (right - left) // 2
        if can_ship(weights, mid, days):
            right = mid          # mid works — try smaller
        else:
            left = mid + 1       # mid too small — try larger

    return left

# --- Example ---
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(min_ship_capacity(weights, 5))   # Output: 15

15

def binary_search_template(search_space_start, search_space_end, condition):
    """
    Find the minimum value in [start, end] where condition(value) is True.
    Assumes: condition is False for small values, True for large values.
    """
    left, right = search_space_start, search_space_end

    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid         # mid satisfies condition — try smaller
        else:
            left = mid + 1      # mid doesn't satisfy — go larger

    return left                 # Smallest value satisfying condition