@jalaj: sorry for delay i was busy these days
the implementation of my method is a bit hard because R2 and R4 which i
mentioned before are not always squares
and in that case we must first break the rectangles into squares and then
perform the search on squares
here breakToSquares function breaks a
Consider the bottom left elment of the given 2 - D array. if it is less than
the number to be search, ignore the whole column and if greater ignore the
whole row. if it is equal note the array index. repeat the above procedure
till all rows and column are scanned. By doing with complexity less tha
@ abv i want less then O(n)
On Mon, Jul 5, 2010 at 8:14 PM, mohit ranjan wrote:
> @ Jalaj
>
>
>
> suppose the matrix is
>
> 0 13 7
> 2 45 8
> 6 9 10 11
>
@ Jalaj
suppose the matrix is
0 13 7
2 45 8
6 9 10 11
8 12 13 14
element to search=9;
start at right-top element i.e curr_elem=7
9>curr_elem, mo
@amir ..could you please provide a rough pseudocode for it... :-?
On Sun, Jul 4, 2010 at 3:12 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @jalaj: oops! i'm sorry but by diameter i meant diagonal!
>
> binary search on the diagonal 0 4 10 14 the result is 4<9<10
> so the
@jalaj: oops! i'm sorry but by diameter i meant diagonal!
binary search on the diagonal 0 4 10 14 the result is 4<9<10
so the matrix that ends with 4:
0 1
2 4
and the matrix that starts with 10:
10 11
13 14
can't have 9 in them
so we continue the search in
3 7
5 8
and
6 9
8 12
applying the search
Young's Tableau.. go along non-major diagonal in a stair up or down fashion
On Fri, Jul 2, 2010 at 11:46 PM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> @Rahul: the worst case running time for your algo is O(nlogn)
>
> but here's another approach:
> suppose we're searchin
not clear yaar
suppose the matrix is 0 1 3 7
2 4 5 8
6 9 10 11
8 12 13 14
how wiill you search 9.. elaborate
On Fri, Jul 2, 2010 at 11:09 PM, Rahul Kushwaha wrote:
> i think this might work
> Bins
@Rahul: the worst case running time for your algo is O(nlogn)
but here's another approach:
suppose we're searching for x
binary search on the diameter of the matrix (note that the diameter is
sorted)
if x is not on the diameter
when you find i such that a[i][i]http://groups.google.com/group/algoge
Consider the bottom half elment of the given 2 - D array. if it is less than
the number to be search, ignore the whole column and if greater ignore the
whole row. if it is equal note the array index. repeat the above procedure
till all rows and column are scanned. By doing with complexity less tha
Consider the bottom half elment of the given 2 - D array. if it is less than
the number to be search, ignore the whole column and if less ignore the
whole row. if it equal note the array index. repeat the above procedure till
all rows and column are scanned. By doing with complexity less than O(n),
i think this might work
Binsearch on matrix for the column in which the element may lie...
use last element of the coloumn for comparisons
\
then binsearch in the coloumn to find if the element is there or not
--
You received this message because you are subscribed to the Google Groups
"
how to search a number in a 2d matrix which is sorted both row wise and
column wise in less then http://groups.google.com/group/algogeeks?hl=en.
13 matches
Mail list logo
