This question already has an answer here:

I am not able to find a clear explanation about Ordered Arrays. All I know is

The array is 1-ordered it is in the usual order. (For the 1st must be less than the 2nd which in turn must be less than the 3rd which ... which must be less than the $n$th.)

But what is 2-ordered, 3-ordered... so on array?

Can someone guide me?


marked as duplicate by David Richerby, jmite, Yuval Filmus, Luke Mathieson, hengxin Dec 28 '14 at 5:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Borrowing the definition from Gaurang Tandon's question:

An array $A[1...n]$ is said to be k-ordered if $$A[i - k] \leq A[i] \leq A[i + k]$$ for all $i$ such that $k < i \leq n - k$.

For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.

I must also say that I've never seen a similar definition before (and I find it to be quite un-useful, but maybe it is important somewhere).

Another definition I have seen, extends the ordering to $k$-dimensional objects. For instance, with two dimensions:

Given vectors $v=(v_1,v_2)$ and $u=(u_1,u_2)$, we say that $v>u$ in a 2-ordering if
$$v_1 > u_1$$ or if $$ v_1=u_1 \text{ and } v_2>u_2$$

Then, an array of vectors $v[1...n]$ is $2$-ordered if for every $i$, $v[i]<v[i+1]$ via the above 2-ordering.


Not the answer you're looking for? Browse other questions tagged or ask your own question.