جست‌وجوی دودویی در پایتون

دو متغیر low و high مرزهای بخشی از لیست را نگه می‌دارند که عدد هنوز ممکن است در آن باشد. در هر دور، mid = (low + high) // 2 را حساب کنید و بر اساس نتیجهٔ مقایسه، یکی از دو مرز را جابه‌جا کنید.

nums = list(map(int, input().split()))
target = int(input())

low = 0
high = len(nums) - 1
answer = -1
while low <= high:
    mid = (low + high) // 2
    if nums[mid] == target:
        answer = mid
        break
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

print(answer)

این جواب چطور کار می‌کند؟

در ابتدا low به اولین و high به آخرین اندیس اشاره می‌کند. در هر دور، mid اندیس عضو وسط این بازه است و تقسیم صحیح // نتیجه را به عدد صحیح تبدیل می‌کند.

اگر عضو وسط از عدد مورد نظر کوچک‌تر باشد، عدد فقط می‌تواند در نیمهٔ بعد از mid باشد و low به mid + 1 می‌رود. اگر بزرگ‌تر باشد، high به mid - 1 می‌آید. برای ورودی نمونه، عضو وسط در دور اول ۱۶ است، در دور دوم ۵۶ و در دور سوم ۲۳ که همان عدد مورد نظر است.

شرط حلقه low <= high است، نه low < high. وقتی بازه به یک عضو برسد، low و high برابرند و آن عضو هم باید بررسی شود. اگر حلقه بدون پیدا شدن عدد تمام شود، answer همان منفی یک باقی می‌ماند.

راه دوم: ماژول bisect

from bisect import bisect_left

nums = list(map(int, input().split()))
target = int(input())

i = bisect_left(nums, target)
if i < len(nums) and nums[i] == target:
    print(i)
else:
    print(-1)

bisect_left همان جست‌وجوی دودویی را انجام می‌دهد و جایی را برمی‌گرداند که عدد باید در آن قرار بگیرد. این جا ممکن است بیرون از لیست یا متعلق به عدد دیگری باشد؛ پس باید بررسی کنید که nums[i] واقعاً همان عدد باشد.