s*******s
发帖数: 27 | 1 Binary Search on 2D Array
How do you apply Binary Search on 2D array supposed you have 2D array with
integers sorted both horizontally and vertically. If you find any occurrence
of the value you are looking for you return true else false. What is the
complexity?
For example the 2D array could look like the following
1 4 5 6
2 5 7 9
3 8 10 11
6 9 12 20 |
h*******e
发帖数: 225 | 2 This is a classic problem. Binary search doesn't really help you in terms of
comlexity. Finding an element in the nxn sorted matrix is Theta(n) using
the diagonal method.
occurrence
【在 s*******s 的大作中提到】
: Binary Search on 2D Array
: How do you apply Binary Search on 2D array supposed you have 2D array with
: integers sorted both horizontally and vertically. If you find any occurrence
: of the value you are looking for you return true else false. What is the
: complexity?
: For example the 2D array could look like the following
: 1 4 5 6
: 2 5 7 9
: 3 8 10 11
: 6 9 12 20
|
s*******s
发帖数: 27 | 3 Could you please give an example of the diagonal method? For example, how to find 6 in the array? Thanks.
of
【在 h*******e 的大作中提到】
: This is a classic problem. Binary search doesn't really help you in terms of
: comlexity. Finding an element in the nxn sorted matrix is Theta(n) using
: the diagonal method.
:
: occurrence
|
h********g
发帖数: 116 | 4 start from bottom left corner, let the value be v,
if xv, move left
【在 s*******s 的大作中提到】
: Could you please give an example of the diagonal method? For example, how to find 6 in the array? Thanks.
:
: of
|
c*****t
发帖数: 1879 | 5
^^^^
guess it is typo, should be right
【在 h********g 的大作中提到】
: start from bottom left corner, let the value be v,
: if xv, move left
|
s*******s
发帖数: 27 | 6 Let me formalize it a bit.
2D array: A[0..n-1, 0..n-1]
Target value: v
Start from bottom left corner. Only movements of up and right are allowed.
Let the array value of current position be a.
do the following:
if a>v, move up;
if a
until find v or hitting the right or top side of the array.
Is it the same to start from top right corner and do the following movement?
if a>v, move left;
if a
until find v or hit the bottom or left side of the array.
【在 h********g 的大作中提到】
: start from bottom left corner, let the value be v,
: if xv, move left
|
