جستجوی خطی و دودویی

جستجوی خطی و دودویی

حجم فایل : 176.8 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 19
بنام خدا ساختمان داده ها

جستجوی خطی و دودویی

مرور مشکل: چگونه داده ی مورد نظر را در یک ساختار داده پیدا کنیم.

جستجوی داده از اعمال اساسی کامپیوترها است.

الگوریتم های جستجوی متفاوتی وجود دارند.

ما الگوریتم ها را بر اساس پیچیدگی آنها مقایسه کنیم.
البته همیشه الگوریتمی که کمترین پیچیدگی دارد برای همه ی انواع داده مناسب نیست. مشاهدات جستجو را می توان در لیست مرتب و یا غیر مرتب انجام داد.
جستجوی لیست غیر مرتب سرراست تر است.
کاربردهای جستجو:
جستجوی اسناد
جستجو در پایگاه داده
کاربردهای مرتب سازی
هر جایی که به سازماندهی داده نیاز داشته باشیم (مثل نتایج جستجوی گوگل) جستجوی خطی از ابتدای لیست شروع کنید و تمام آیتمها را امتحان کنید.
بدترین حالت و حالت میانگین مثل هم هستند.
معمولاً به این جستجو جستجوی ترتیبی گفته می شود.
چگونه یکی از عناصر آرایه را پیدا کنیم؟ شبه کد جستجوی خطی در آرایه int LinearSearch( int key, int[ ] db ) {
int index;
for( index=0; index<db.length; index++ ) {
if( db[index]==key )
return index;
}
return –1;
} جستجوی خطی در لیست مرتب بدترین حالت
خیلی بهتر از نسخه ی قبلی نیست.
حالت میانگین برابر O(n) است البته بر دو تقسیم شده است. جستجوی خطی در لیست پیوندی DNode LinearSearch( String key, SLList db ) {
DNode probe = db.head;
while ( probe!=null ) {
if( probe.value.equals(key) )
return probe;
probe = probe.next;
}
return null;
} B B head C A 1 2 3 target بهترین حالت: O(1)
بدترین حالت: O(n)
میانگین: O(n) جسنجوی دودویی اگر رکوردها مرتب باشند می توانیم بهتر عمل کنیم.
به نحوه ی استفاده از فرهنگ لغت دقت کنید.
اگر عنصر مورد نظر در لیست باشد، بین نمایه های ‘low’ و ‘high’ قرار دارد. جستجوی دودویی: حالت اول فرض کنید دنبال M می گردیم. جستجوی خطی: حالت دوم فرض کنید دنبال ‘E’ می گردیم. جستجوی خطی: حالت دوم فرض کنید دنبال ‘P’ می گردیم. از آنجا که عنصر مورد نظر از عنصر وسط بزرگتر است، ما می دانیم که عنصر در نیمه ی سمت چپ نیست. لذا فقط در نیمه ی سمت راست دنبال آن می گردیم:
low = middle + 1; جستجوی دودویی: مثال شبه کد جستجوی دودویی int BinarySearch(char target, char[] array) {
    int low=0, high = array.length-1, middle;
    while (low <= high) {
        middle = (low+high)/2;
        if( array[middle]==target )
            return middle;
        else if( array[middle]            low = middle + 1;
        else
            high…