Array balancing point
<p>What is the best way to solve this?
A balancing point of an N-element array A is an index i such that all elements on lower indexes have values &lt;= A[i] and all elements on higher indexes have values higher or equal A[i].</p>

<p>For example, given:</p>

<p>A[0]=4 A[1]=2 A[2]=7 A[3]=11 A[4]=9</p>

<p>one of the correct solutions is: 2. All elements below A[2] is less than A[2], all elements after A[2] is more than A[2].
One solution that appeared to my mind is O(nsquare) solution. Is there any better solution?</p>
