جستجو به روش تقسیم و حل؟

[kluivert]

الگوریتمی بنویسید که لیست مرتب شده ای از n عنصر را با تقسیم آن به سه لیست فرعی با حدود n/3 عنصر جستجو کند....این الگوریتم لیست فرعی حاوی عنصر را یافته و آن را به سه لیست فرعی تقسیم می کندبا اندازه های مساوی....این سوال از قسمت جستجوی دودویی نیپولیتان است ....در مورد این سوال نمی توانیم از تقسیم و حل استفاده کنیم به خاطر اینکه مساله به n/c تقسیم شده اگه میشه منو راهنمایی کنید

[mortezamsp]

در روش تقسیم و حل ، مقدار زیرمساله ها باید بیشتر یا مساوی 2 باشه. بنابراین اینجا میتونی از روش تقسیم و حل استفاده کنی.

[Blunch]

با سلام خدمت دوست گرامي!

بنظر من جواب سوال شما همانند روش merge sort منتها بجاي اينكه ليست هربار به n/2
تقسيم شود تقسيم بر 3 ميشود البته نميدونم درست هست يا نه ، ولي اميدوارم لا اقل بتونه كمكتون كند !



index TriplySearch(index low,index high)
{
index mid1,mid2;
while(low <= high && high-low > 1)
{
mid1 = (low+high) / 3;
mid2 = 2 * (low+high) / 3;
if(x == S[mid1])
return mid1;
else if(x == S[mid2])
return mid2;
if(x < S[mid1])
high = mid1 -1;
else if(x < S[mid2])
high = mid2 -1;
if(x > S[mid2])
low = mid2 +1;
else if(x > S[mid1])
low = mid1 +1;
}
for(mid1=low;mid1<=high;mid1++)
if(x==S[mid1])
return mid1;
return 0;
}

[pesar irooni]

merge sort??!! که نه احتمالا منظورتون binary search هست. چون ورودی ما لیست مرتب شده است.
فقط فرقش با جستجوی دودویی اینه که لیست رو به سه قسمت تقسیم میکنیم و هر دفعه حداکثر دو مقایسه انجام میدیم چون دو نقطه میانی داریم. از همون مرتبه o(logn) هم هست. مثل جستجوی دودویی هم بصورت بازگشتی میشه حلش کرد و هم بصورت تکراری.

min = 1;
max = N; //array size
repeat
mid1 = min + (max-min) / 3
mid2 = min + 2(max-min) / 3 //or mid2 = min + 2 mid1
if x > A[mid2] then
min := mid2 + 1
else
if x < A[mid1] then
max := mid1 - 1;
else
max := mid2 - 1;
min := mid1 + 1;
until (A[mid1] = x) or (A[mid1] = x) or (min > max);
if A[mid1] = x return mid1
else
if A[mid2] = x return mid2
else return not found;