بهترين حالت و بدترين حالت و ميانگين -جست و جوي دودويي ؟

[dezchilds]

سلام
به نظر شما بهترين حالت و بدترين حالت و حالت ميانگين براي الگوريتم جست و جوي دودويي چي هست

[Farzandekurosh]

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

[مسعود اقدسی فام]

بهترین حالت : کلید مورد جستجو در وسط لیست باشد .
بد ترین حالت : کلید مورد جستجو در لیست نباشد .
حالت میانگین : ندارد . البته فکر کنم . یه سرچ بزن
میانگین این می‌شه که اگه در فلان خانه باشه چقدر هزینه داره. مجموع همه اونها تقسیم بر همه حالتها می‌شه میانگین.

[Farzandekurosh]

یه کم بیشتر توضیح میدین

[مسعود اقدسی فام]

یه کم بیشتر توضیح میدین

جستجوی ترتیبی رو در نظر بگیرید. اگه x همون خانه‌ی اول باشه، با یه مقایسه پیدا می‌شه. اگه خانه‌ی دوم باشه، با دومین مقایسه پیدا می‌شه، و همینطور اگه خانه‌ی iام باشه، با i مقایسه پیدا می‌شه. در انتها اگه در خانه‌ی n ام باشه یا اصلا وجود نداشته باشه، n مقایسه صورت می‌گیره. یعنی در کل 1 + 2 + 3 + ... + n مقایسه داریم که روی n عنصر انجام شده. این مجموع یه تصاعد عددیه که نتیجه می‌ده: n ( n + 1 ) / 2.
این تعداد مقایسه رو به n تقسیم کنید n + 1 / 2 به دست می‌یاد که در اصطلاح گفته می‌شه متوسط مقایسه‌ی مورد نیاز برای پیدا کردن عنصر مطلوب در یک آرایه‌ی n عنصری به روش جستجوی ترتیبیه.