binear search در ماتریس

[xnazaninx]

کسی میدونه با استفاده از روش binary search چطوری میشه عددی مانند x رو در یک ماتریس n*n پیدا کرد که سطر و ستوناش مرتباً و هزینه اش هم از n^2 کمتر باشه؟؟؟
اگه کسی میدونه ممنون میشم کمک کنه:لبخندساده:

[Developer Programmer]

یه نمونه از ماتریس مورد نظرتون رو بذارین

[xnazaninx]

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

5 4 3 2 1
14 13 12 11
21 20 19 18
25 24 23 22

n*n باشه و سطر و ستوناش به صورت صعودی مرتب شده باشه از روش "divide & conquer"

[xnazaninx]

نمیشه یه نفر جواب سوال منو بده؟؟؟
اینقد سوالم سخته؟؟؟:گریه::ناراحت:

[Developer Programmer]

برای پیدا کردن یه عنصر، اون رو به اولین و آخرین عنصر هر سطر مقایسه کنین تا بدونین در کدام طر دنبلش بگردین. اما اینکه قطعا 2^n میشه یا نه... نمیدونم.

[manager]

مطابق با الگوریتم جستجوی دودوئی برای آرایه خطی عمل کن با این تفاوت که :

Left := 0 ;
Right := n*n-1 ;
while(right>left) do
begin
middle := [(right+left) / 2];
row :=[middle / n];
column := middle mod n;

if(matrix[row][column]==item) then item found;
else if (matrix[row][column]<item) then left=middle;
else if (matrix[row][column]>item) then right=middle;
end while;

زمان مصرفی این الگوریتم (Ө(logn هست.