Chương trình tìm chỉ số nhỏ nhất mà giá trị phần tử bằng chỉ số trong Python

Cho danh sách nums các số duy nhất, sắp xếp tăng dần. Tìm i nhỏ nhất sao cho nums[i] == i. Nếu không có, trả về -1. Yêu cầu độ phức tạp O(log n).

Ví dụ: nums = [-4, -1, 2, 3, 8] → kết quả 2 (cả nums[2]=2 và nums[3]=3 nhưng 2 nhỏ hơn).

Thuật toán giải quyết (Binary Search / Tìm kiếm nhị phân)

1. Khởi tạo ret = -1, lhs = 0, rhs = len(nums)-1
2. Khi lhs <= rhs:
   • mid = (lhs + rhs) // 2
   • Nếu nums[mid] == mid: ret = mid (ghi nhận, tiếp tục tìm bên trái)
   • Nếu nums[mid] >= mid: rhs = mid - 1
   • Ngược lại: lhs = mid + 1
3. Trả về ret

Tính chất đơn điệu: nums[i] - i không giảm vì nums tăng chặt.

Ví dụ minh họa

def solve(nums):
    ret = -1
    lhs = 0
    rhs = len(nums) - 1
    while lhs <= rhs:
        mid = (lhs + rhs) // 2
        if nums[mid] == mid:
            ret = mid
        if nums[mid] >= mid:
            rhs = mid - 1
        else:
            lhs = mid + 1
    return ret

nums = [-4, -1, 2, 3, 8]
print(solve(nums))

Đầu vào

[-4, -1, 2, 3, 8]

Đầu ra

2