الگوریتم جستجو دودویی چیست ؟

الگوریتم جستجوی دودویی یک الگوریتم کارآمد برای جستجو در یک لیست مرتب (مثلاً یک آرایه) استفاده می‌شود. در این الگوریتم، میانه لیست گرفته می‌شود و با مقایسه میانه با عنصر مورد نظر، جستجو در نصف لیست که احتمالاً حاوی عنصر مورد نظر است، انجام می‌شود. این عمل به صورت بازگشتی ادامه می‌یابد تا عنصر مورد نظر پیدا شود یا لیست به یک عنصر یا لیست خالی برسد.

الگوریتم جستجوی دودویی به شکل زیر عمل می‌کند:

۱. مقدار میانه لیست را محاسبه می‌کنیم.
۲. اگر مقدار میانه با عنصر مورد نظر برابر باشد، عنصر پیدا شده است. الگوریتم پایان می‌یابد.
۳. اگر مقدار میانه از عنصر مورد نظر کمتر باشد، جستجو را در نصف بالایی لیست (اعداد بزرگتر) انجام می‌دهیم.
۴. اگر مقدار میانه از عنصر مورد نظر بیشتر باشد، جستجو را در نصف پایینی لیست (اعداد کوچکتر) انجام می‌دهیم.
۵. این مراحل را به صورت بازگشتی ادامه می‌دهیم تا عنصر مورد نظر پیدا شود یا لیست به یک عنصر یا لیست خالی برسد.

حالا یک مثال کد در زبان پایتون:

def binary_search(arr, target):
   left, right = 0, len(arr) - 1
   while left <= right:
       mid = (left + right) // 2  # Calculate the middle of the list
       # Target element found
       if arr[mid] == target:
           return mid
       # If the middle element is smaller than the target, search in the upper half of the list
       elif arr[mid] < target:
           left = mid + 1
       # Otherwise, search in the lower half of the list
       else:
           right = mid - 1
   # Target element not found
   return -1
# Example of using the function
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
if result != -1:
   print(f"Element {target} found at index {result}.")
else:
   print("Target element not found.")

در این مثال، الگوریتم جستجوی دودویی در یک لیست مرتب اعداد جستجوی عدد ۷ را انجام می‌دهد. نتیجه این مثال این است که عدد ۷ در اندیس ۳ یافت شده است.