Sorted Array-இல் Classic Binary Search

Classic binary search O(log n) steps-இல் index கண்டுபிடிக்கும் அல்லது இல்லை என நிரூபிக்கும். ஒவ்வொரு compare-யும் பாதி indices-ஐ நீக்கும்.

Try this in Python

def first_index_ge(sorted_arr: list[int], x: int) -> int | None:
    """First index with value >= x, or None if all smaller."""
    lo, hi = 0, len(sorted_arr) - 1
    ans = None
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_arr[mid] >= x:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans


print(first_index_ge([2, 4, 4, 7], 5))

Key takeaways

• ஒரே loop; move rule goal-ஐப் பொறுத்து மாறும்.
• குறியீடு எழுதும் முன் காகிதத்தில் சிறிய array வரையுங்கள்.
• len==0, len==1 test செய்யுங்கள்.