โปรแกรมหา Index น้อยที่สุดที่ค่าเท่ากับ Index ใน Python

ให้ลิสต์ nums เรียงเพิ่มขึ้น ไม่ซ้ำ หา i น้อยที่สุดที่ nums[i] == i (O(log n) ด้วย Binary Search)

ตัวอย่าง: nums=[-4,-1,2,3,8] → 2 (nums[2]=2 และ nums[3]=3 แต่ 2 น้อยกว่า)

ขั้นตอน (Binary Search)

1. ret=-1, lhs=0, rhs=len(nums)-1
2. วน while lhs <= rhs:
   • mid = (lhs+rhs)//2
   • ถ้า nums[mid] == mid: ret = mid
   • ถ้า nums[mid] >= mid: rhs = mid-1 (ค้นซ้าย)
   • มิฉะนั้น: lhs = mid+1
3. คืน ret

ตัวอย่างโค้ด

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))  # Output: 2

อินพุต

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

เอาต์พุต

2