نحوه پیاده سازی جستجوی باینری با استفاده از روش تکراری

یکی از اساسی ترین الگوریتم ها در علوم کامپیوتر، الگوریتم جستجوی باینری است. شما می توانید جستجوی باینری را با استفاده از دو روش پیاده سازی کنید: روش تکراری و روش بازگشتی. در حالی که هر دو روش پیچیدگی زمانی یکسانی دارند، روش تکراری از نظر پیچیدگی فضا بسیار کارآمدتر است.

یکی از اساسی ترین الگوریتم ها در علوم کامپیوتر، الگوریتم جستجوی باینری است. شما می توانید جستجوی باینری را با استفاده از دو روش پیاده سازی کنید: روش تکراری و روش بازگشتی. در حالی که هر دو روش پیچیدگی زمانی یکسانی دارند، روش تکراری از نظر پیچیدگی فضا بسیار کارآمدتر است.

روش تکراری دارای پیچیدگی فضایی O(1) در مقایسه با O(logn) تولید شده توسط روش بازگشتی است. بنابراین، چگونه می توانید الگوریتم جستجوی باینری را با استفاده از روش تکراری در C، C++ و Python پیاده سازی کنید؟

جستجوی باینری چیست؟

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

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

به طور مشابه، اگر عنصر جستجو از عنصر میانی کوچکتر باشد، به این معنی است که تمام عناصر سمت راست بزرگتر از عنصر جستجو هستند. بنابراین، با تغییر حد بالایی به موقعیت قبلی عنصر میانی، کنترل به سمت چپ آرایه منتقل می‌شود.

این تعداد مقایسه‌ها را در مقایسه با اجرای جستجوی خطی که در آن تعداد مقایسه‌ها برابر با تعداد عناصر در بدترین سناریو است، به شدت کاهش می‌دهد. این روش برای یافتن اعداد در دفترچه تلفن یا کلمات در فرهنگ لغت بسیار مفید است.

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

جستجوی باینری با استفاده از C

مراحل زیر را برای پیاده سازی جستجوی باینری با استفاده از C دنبال کنید:

کل کد منبع برنامه جستجوی باینری با استفاده از C، C++، جاوا و پایتون در این موجود است.
مخزن GitHub
.

این برنامه تابعی به نام ()binarySearch را تعریف می کند که یا شاخص مقدار یافت شده یا -1 را در صورت عدم وجود آن برمی گرداند:

#include <stdio.h>
 
int binarySearch(int arr[], int arr_size, int search_number) {
    /* ... */
}

این تابع با محدود کردن مکرر فضای جستجو کار می کند. از آنجایی که جستجوی باینری روی آرایه های مرتب شده کار می کند، می توانید وسط را محاسبه کنید که در غیر این صورت منطقی نیست. می توانید از کاربر یک آرایه مرتب شده بخواهید یا از الگوریتم های مرتب سازی مانند مرتب سازی حباب یا انتخاب استفاده کنید.

متغیرهای کم و زیاد شاخص هایی را ذخیره می کنند که مرزهای فضای جستجوی فعلی را نشان می دهند. mid ایندکس را در وسط ذخیره می کند:

    int low = 0, high = arr_size - 1, mid;

حلقه اصلی while() فضای جستجو را محدود می کند. اگر مقدار شاخص پایین از شاخص بالا بیشتر شود، فضای جستجو تمام شده است، بنابراین مقدار نمی تواند وجود داشته باشد.

    while (low <= high) {
        /* continues... [1] */
    }
 
    return -1;

پس از به‌روزرسانی نقطه میانی در ابتدای حلقه، سه نتیجه ممکن وجود دارد:

1. اگر مقدار در نقطه میانی همان چیزی است که به دنبال آن هستیم، آن شاخص را برگردانید.
2. اگر مقدار نقطه میانی بیشتر از مقدار مورد نظر ما باشد، مقدار زیاد را کاهش دهید.
3. اگر مقدار وسط کمتر است، مقدار پایین را افزایش دهید.

        /* [1] ...continued */
        mid = (low + (high - low)) / 2;
 
        if (arr[mid] == search_number)
           return mid;
        else if (arr[mid] > search_number)
           high = mid - 1;
        else
           low = mid + 1;

عملکرد را با ورودی کاربر تست کنید. از scanf() برای دریافت ورودی از خط فرمان، از جمله اندازه آرایه، محتویات آن و یک عدد برای جستجو استفاده کنید:

int main() {
   int arr[100], i, arr_size, search_number;
   printf("Enter number of elements: ");
   scanf("%d", &arr_size);
   printf("Please enter numbers: ");
 
   for (i = 0; i < arr_size; i++) {
       scanf("%d", &arr[i]);
   }
 
   printf("Enter number to be searched: ");
   scanf("%d", &search_number);
 
   i = binarySearch(arr, arr_size, search_number);
 
   if (i==-1)
       printf("Number not present");
   else
       printf("Number is present at position %d", i + 1);
 
   return 0;
}

اگر شماره را پیدا کردید، موقعیت یا نمایه آن را نمایش دهید، در غیر این صورت پیامی مبنی بر اینکه شماره وجود ندارد.

جستجوی باینری با استفاده از C++

می‌توانید با وارد کردن Input Output Stream، برنامه C را به یک برنامه C++ تبدیل کنید و از namespace std استفاده کنید تا از تکرار چندین بار آن در برنامه جلوگیری کنید.

#include <iostream>
using namespace std;

از cout با عملگر استخراج << به جای printf() و cin با عملگر درج >> به جای scanf() استفاده کنید و برنامه C++ شما آماده است.

printf("Enter number of elements: ");
cout << "Enter number of elements: ";

scanf("%d", &arr_size);
cin >> arr_size;

جستجوی باینری با استفاده از پایتون

از آنجایی که پایتون از آرایه ها پشتیبانی داخلی ندارد، از لیست ها استفاده کنید. یک تابع، binarySearch() تعریف کنید که سه پارامتر، لیست، اندازه آن و یک عدد را برای جستجو می پذیرد:

def binarySearch(arr, arr_size, search_number):
    low = 0
    high = arr_size - 1
    while low <= high:
        mid = low + (high-low)//2
        if arr[mid] == search_number:
            return mid
        elif arr[mid] > search_number:
            high = mid - 1
        else:
            low = mid + 1
    return -1

دو متغیر کم و زیاد را راه‌اندازی کنید تا به عنوان کران پایین و بالای لیست استفاده شود. مشابه پیاده سازی C، از حلقه while استفاده کنید که فضای جستجو را محدود می کند. mid را برای ذخیره مقدار میانی لیست مقداردهی کنید. پایتون عملگر (//) تقسیم طبقه را فراهم می کند که بزرگترین عدد صحیح ممکن را ارائه می دهد.

مقایسه ها را انجام دهید و فضای جستجو را محدود کنید تا مقدار وسط برابر با شماره جستجو شود. اگر شماره جستجو موجود نباشد، کنترل -1 را برمی‌گرداند.

arr_size = int(input("Enter number of elements: "))
arr=[]
print("Please enter numbers: ", end=" ")
for i in range(0,arr_size):
    arr.append(int(input()))
search_number = int(input("Enter number to be searched: "))
result = binarySearch(arr, arr_size, search_number)

if result == -1:
    print("Number not present")
else:
    print("Number is present at position ", (result + 1))

عملکرد را با ورودی کاربر تست کنید. از input() برای دریافت اندازه لیست، محتویات آن و یک عدد برای جستجو استفاده کنید. از int() برای تایپ کردن ورودی رشته ای که پایتون به عنوان پیش فرض پذیرفته است به یک عدد صحیح تایپ کنید. برای افزودن اعداد به لیست، از تابع append() استفاده کنید.

()binarySearch را فراخوانی کنید و آرگومان ها را ارسال کنید. اگر شماره را پیدا کردید، موقعیت یا نمایه آن را نمایش دهید، در غیر این صورت پیامی مبنی بر اینکه شماره وجود ندارد.

خروجی الگوریتم جستجوی باینری

خروجی الگوریتم جستجوی دودویی زمانی که عنصر در آرایه وجود دارد به صورت زیر است:

خروجی الگوریتم جستجوی باینری در مواردی که عنصر در آرایه وجود ندارد، به شرح زیر است:

ساختارها و الگوریتم های داده های بنیادی را بیاموزید

جستجو یکی از اولین الگوریتم‌هایی است که یاد می‌گیرید و اغلب در مسابقات کدنویسی، قرار دادن و مصاحبه‌ها از شما خواسته می‌شود. برخی از الگوریتم‌های دیگری که باید یاد بگیرید عبارتند از: مرتب‌سازی، هش کردن، برنامه‌نویسی پویا، تطبیق رشته‌ها و الگوریتم‌های آزمایش اولیه.

علاوه بر این، درک پیچیدگی زمانی و مکانی الگوریتم‌ها ضروری است. آنها یکی از حیاتی ترین مفاهیم در علوم کامپیوتر در تعیین کارایی هر الگوریتمی هستند. با دانش ساختار داده ها و الگوریتم ها، شما موظف به ساخت بهترین برنامه ها هستید.

منبع مقاله