سبد خرید

بستن سبد خرید

هیچ محصولی در سبد خرید نیست.

تعداد محصول: 0 کل قیمت: تومان0

الگوریتم و کد جستجوی دودویی (باینری)

الگوریتم و کد جستجوی دودویی (باینری) ، در این در این مطلب، الگوریتم جستجوی دودویی (Binary Search) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان های برنامه‌نویسی ++C و جاوا انجام شده است.

جستجوی دودویی

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

الگوریتم و کد جستجوی دودویی به زبان ++C و جاوا

پیشتر گفتیم که ساده ترین راه برای جستجو در یک آرایه استفاده از جستجوی خطی است اما مرتبه زمانی این الگوریتم O(n) است و برای آرایه های بزرگ مناسب نیست. روش دیگری به صورت استفاده از جستجوی دودویی یا همان باینری سرچ است که زمان جستجو را به میزان قابل توجهی کاهش می دهد.

جستجوی دودویی چگونه عمل میکند؟

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

  1. x را با عنصر میانی آرایه مقایسه میکنیم.
  2. اگر با x برابر بود ایندکس آن خانه را برمیگردانیم.
  3. اگر از x کوچکتر بود نیمه سمت راست آرایه و در غیر این صورت نیمه سمت چپ آرایه را انتخاب میکنیم.
  4. سه مرحله بالا را برای نیمه انتخاب شده تا زمانی انجام میدهیم که عنصر مورد نظر در آرایه پیدا شود.
  5. اگه عنصر پیدا نشد مقدار -۱ را برمیگردانیم.

کد جستجوی دودویی به زبان++C:

#include <iostream> 
using namespace std; 
  
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        if (arr[m] == x) 
            return m; 
  
        if (arr[m] < x) 
            l = m + 1; 
  
        else
            r = m - 1; 
    } 
  
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

 

کد جستجوی دودویی به زبان ++C (بازگشتی):

#include <iostream> 
using namespace std; 

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        if (arr[mid] == x) 
            return mid; 
  
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 

        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

 

کد جستجوی دودویی به زبان جاوا:

class BinarySearch { 

    int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            if (arr[m] == x) 
                return m; 
  
            if (arr[m] < x) 
                l = m + 1; 
  
            else
                r = m - 1; 
        } 
  
        return -1; 
    } 
  
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at "
                               + "index " + result); 
    } 
}

 

نکته:

مرتبه زمانی: مرتبه زمانی جستجوی دودویی O(Log n) است و از فرمول T(n) = T(n/2) + c بدست می آید.

پست های مشابه

19تیر 1400

CSS چیست و نقش آن در طراحی وب سایت که در این پست، طراحی و ساخت سایت را توضیح می دهیم، پس با ما همراه باشید. امروزه نرم افزارهایی برای طراحی وب سایت پدید آمده است که این امکان را می دهد که حتی بدون نیاز به دانش برنامه نویسی وب سایتی تولید و توسعه […]

265

0

18فروردین 1400

از آنجايي که دانشجويان زيادي جهت سفارش پروژه هاي C++ به سايت مراجعه نموده اند، در این مطلب پروژه ای مربوط به تبدیل اعداد دهدهی به اعداد دودویی است که در اختیار شما دوستان قرار دادیم…

560

0

2اسفند 1399

بدست آوردن تعداد بیشترین مقسوم علیه دربین چند عدد با پایتون که بسیاری از دانشجویان به دنبال این سورس کد هستند. در این مقاله…

3403

2

دیدگاه و پرسش