Chương trình Python tìm chỉ số chèn để giữ danh sách đã sắp xếp

Cho danh sách nums đã sắp xếp tăng dần và số target. Tìm chỉ số lớn nhất để chèn target vào nums mà vẫn giữ thứ tự sắp xếp. Yêu cầu: O(log n), không dùng thư viện.

Ví dụ

nums = [1,5,6,6,8,9], target = 6 → Output: 4

Chèn tại index 4: [1,5,6,6,6,8,9] (sau các 6 hiện có).

Thuật toán: Binary Search Upper Bound

Tìm vị trí đầu tiên > target (upper bound). Chỉ số chèn = vị trí đó.

Code Python

def solve(nums, target):
    left, right = 0, len(nums) - 1
    ans = 0  # mặc định chèn ở đầu
    
    while left <= right:
        mid = (left + right) // 2
        if target >= nums[mid]:
            ans = mid + 1      # chèn sau mid
            left = mid + 1     # tìm bên phải
        else:
            right = mid - 1    # tìm bên trái
    
    return ans

# Test
print(solve([1,5,6,6,8,9], 6))  # 4
print(solve([1,5,6,6,8,9], 7))  # 4 (chèn giữa 6 và 8)
print(solve([1,5,6,6,8,9], 0))  # 0 (chèn đầu)
print(solve([1,5,6,6,8,9], 10)) # 6 (chèn cuối)

Giải thích

• ans lưu chỉ số chèn tiềm năng (mid + 1 khi target >= nums[mid]).
• Khi target >= nums[mid]: target nên ở bên phải mid → cập nhật ans, dịch left.
• Khi target < nums[mid]: target ở bên trái → dịch right.
• Kết thúc: ans là upper bound (vị trí đầu tiên > target).

So sánh với bisect module

import bisect
bisect.bisect_right([1,5,6,6,8,9], 6)  # 4 - giống solve()
bisect.bisect_left([1,5,6,6,8,9], 6)   # 2 - vị trí đầu tiên >= target

Hàm solve() tương đương bisect_right().

Độ phức tạp

• Thời gian: O(log n)
• Không gian: O(1)