باینری سرچ و فیبوناچی سرچ

[Shahab_H]

با سلام
من نیاز به الگوریتم باینری سرچ و فیبوناچی سرچ دارم
لطفا اگر کد می ذارید C باشه
لطفا توضیح کامل الگوریتم ها رو هم بدین
به علاوه ی بررسی پیچیدگی زمانی یا time complexity یا big Oh این الگوریتم ها که در درس یاختمان داده ها بررسی میشه
دوستان هر قسمتش هم که باشه غنیمته
ممنون

[hamidreza_buddy]

سرچ باینری چون روی یه لیست مرتب شده انجام میشه و در هر دفعه فضای جستجو رو نصف می کنه، در نتیجه پیچیدگی زمانیش O(lgn) هست.

اینجوری که مثلاً برای یه آرایه i تا j اگه عنصر s برابر [ x[(i+j)*2 بود که جستجو تمومه. اگه s بزرگتر بود باید سمت چپ رو بگردیم. اگه s کوچکتر بود باید سمت راست رو بگردیم . (مثل جستجو توی یه دیکشنری).

شبه کدش به صورت زیر هست. تبدیلش به کد سی کاری نداره.

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[فاطـمه]

این رو ببین:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[فاطـمه]

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

---------------------------------------------------------------
خب تا اینجا فیبوناچی بود حالا باینری:
اول این رو ببین:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

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

[Shahab_H]

ممنون از همه ی دوستان
واقعا لطف کردید
اگر براتون ممکنه می تونینین همینارو به خصوص فیبوناچی رو مرحله به مرحله به فارسی بگین که چی کار می کنه؟

[Shahab_H]

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

[فاطـمه]

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

دوست من بگو کدومشون به دردت خوره همون رو ترجمه کنم

[Shahab_H]

خیلی ممنون از لطفتون
من کلا نحوه ی سرچ فیبوناچی رو متوجه نشدم که چی کار می کنه

[Shahab_H]

دوستان لطفا سریع تر جواب بدین من وقت ندارم :(

[hamidreza_buddy]

خیلی ممنون از لطفتون
من کلا نحوه ی سرچ فیبوناچی رو متوجه نشدم که چی کار می کنه

الگوریتمش رو اینجا کاربر فاطمه گفته:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

اگه یه کم با دقت مطالعش کنید متوجه میشیه. الگوریمش شبیه الگوریتم جستجوی باینری هست (اون که خیلی ساده هست و امیدوارم بدونین چه جوریه). با این تفاوت که به جای اینکه از وسط آرایه رو نصف کنه از اعداد فیبوناتچی برای این کار استفاده می کنه. از مرتبه log n هست. همون طور که در الگوریتم بالا می بینید تا مرحله چهار چک می کنه که آیا این عنصر برابر عنصر مورد نظر یا خیر. اگه نباشه می ره به قدم 5. در ایون جا هم بر حسب اینکه از اون عدد کوچیکتره یا بزرگتر تصمیم می گیره که یه قسمت از آرایه رو دیگه جستجو نکنه (مثل جستجوی باینری).