با سلام:
ارایه مرتب A داده شده است. تابع زیر برای جستجوی دودویی در A( از اندیس L تا R )برای پیدا کردن x نوشته شده است .
کد:
function search (x:real;L,R:integer):boolean;
var M:integer;
begin
M:=(L+r)div 2;
if (x=a[M])then return (true);
if (x<a[M] and (M>L)) then return (search (n,L,m-1));
if (x>a[M] and (m<R)) then return (search (n,M+1,r));
return (False)
end;کد:
a[1..n]۱-اگر x در ارایه باشد . همواره با حداکثر( O(lgn پیدا می شود .
۲-اگر x در ارایه نباشد و پاسخ false وبا حداکثر O(lgn) مقایسه بدست میاید .
۳- در جستجوی نا موفق برای دو مقدار متفاوت x که در ارایه موجود است. همواره تعداد مقایسهها برابر است .
۴-حداکثر تعداد مقایسهها (چه موفق چه نا موفق )همواره از O(n) کمتر است .
جواب این سوال گزینه ۳ میشه ولی من نمیدونم چرا ؟؟ اصلا منظور از تعداد مقایسه در حالت ناموفق یعنی چه ؟؟
جستجوی ناموفق یعنی چیزی رو جستجو کنیم که در آرایه نباشد و تابع عدد ۱- را برمیگرداند.
شما یه سری عدد مرتب در آرایه دارید روش جستجوی دودویی رو که بلدید حالا یه عددی که در آرایه نیست رو میخواهید جستجو کنید مثلا
۱و۳و۵و۷ در آرایه قرار دارد شما اگر بخواهید ۴ را جستجو کنید دو مقایسه دارید (مقایسه با ۳ و ۵)
ولی اگر ۸ را جستجو کنید ۳ مقایسه دارید( با ۳ و۵ و۷ )
پس دیدید که برای دو عدد متفاوت در جستجوی ناموفق تعداد مقایسهها لزوما یکسان نیست.(فکر کنم حداکثر یک اختلاف دارد)