جستجوی دودویی (Binary Search)
«جستجوی دودویی (Binary Search)» روی آرایه «مرتب (Sorted)» کار می کند. هر بار وسط را می سنجد. سپس نصف نادرست را کنار می گذارد. بنابراین سرعتش خیلی خوب است.
ایده اصلی جستجوی دودویی
وسط آرایه را نگاه کن. اگر مقدارِ وسط برابر هدف بود، تمام است. اگر مقدارِ وسط کوچک تر بود، نیمه راست را بگرد. اگر بزرگ تر بود، نیمه چپ را بگرد. هر بار ناحیه جستجو نصف می شود.
پیاده سازی پایتون
کد زیر همان الگوریتم منبع است. حواست باشد آرایه باید مرتب باشد.
def binarySearch(arr, targetVal):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == targetVal:
return mid
if arr[mid] < targetVal:
left = mid + 1
else:
right = mid - 1
return -1
mylist = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 11
result = binarySearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
گام های عملی
- لیست «مرتب» آماده کن.
- هدف را مشخص کن.
- وسط را حساب کن.
- مقایسه کن و نیمه نادرست را حذف کن.
- تکرار تا یافتن یا اتمام ناحیه.
پیچیدگی زمانی
هر مقایسه ناحیه را نصف می کند. بنابراین «پیچیدگی (Complexity)» زمانی O(\log_2 n) است. روی داده مرتب، بسیار سریع تر از جستجوی خطی است.
نکته: اگر آرایه مرتب نیست، اول مرتب کن یا از جستجوی خطی استفاده کن.
پیوندها
جستجوی دودویی، مرجع این صفحه. همچنین برای مقایسه به جستجوی خطی سر بزن.
منبع W3Schools: Binary Search و شبیه سازی مرحله ای.
جمع بندی سریع
- الزاماً روی آرایه مرتب.
- هر بار نصف می کند.
- سرعت بدترین حالت: O(log n).
- برای وجود سریع تر از خطی.
- برای نامرتب ها، اول مرتب کن.