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 هست.