How can I apply binary search to find two adjacent increasing elements in an unsorted array?

Question

I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ if there are multiple).
We know that: in $a$ there are at least $2$ elements, $a$ may or may not be sorted and the first element in $a$ is less than the last element.

The solution needs to have $O(\log n)$ time-complexity and $O(1)$ space-complexity.

Example $a=[0,-8,-8,6,1]$, the function returns $2$ because $a[2]<a[3]$.

My Thoughts:

• I need to somehow "split" the problem in half by cutting half of the numbers that I need to check in order to reach the required time complexity.

• The array isn't ordered, but I have information that the first element is less than the last, and that there are at least two elements, so I need to somehow use this extra info.

  The unsorted information is not allowing me to reach anything, I can definitely start from the middle and check if it's less than the last element, if yes then an index $i$ that satisfies $a[i]<a[i+1]$, will surely appear on the right side, but I can't just jump over half of the numbers to the right, they're unsorted, so the index $i$ might be the next one from the middle.
  

Answer 1

You are almost there. "If yes then an index $i$ that satisfies $a[i]<a[i+1]$, will surely appear on the right side"; so continue searching on the right side. If no, continue searching on the left side.

Binary Search

The idea is to find two elements, the left of which is smaller than the right of which such that their positions are becoming closer and closer. In the end, they must have become adjacent.

Initially, we have pair $A[0]$ and $A[n-1]$. If $A[0]$ and $A[n-1]$ are adjacent, we are done.

Let the middle index be $m=\lfloor\frac{0+(n-1)}2\rfloor=\lfloor\frac{n-1}2\rfloor$. Consider the element in the middle, $A[m]$.

• If $A[m]<A[n-1]$, we have a new pair $A[m]$ and $A[n-1]$.
• Otherwise, $A[m]\ge A[n-1]\gt A[0]$. We have a new pair $A[0]$ and $A[m]$.

As long as $A[0]$ and $A[n-1]$ are not adjacent, $A[m]$ cannot be $A[0]$ nor $A[n-1]$. So the distance between the new pair of elements must be smaller than the distance between $A[0]$ and $A[n-1]$.

Repeat the process with the new pair of elements. And so on.

Since the distance of the two elements in a pair becomes smaller and smaller by each iteration as long as the pair at the start of the iteration are not adjacent, the pair will become adjacent eventually, at which time we have obtained a wanted pair.

Well, we are applying binary search. A quick analysis shows it takes at most $\lceil\log_2(n-1)\rceil$ iterations to reach a wanted pair.

Two exercises.

Exercise 1(easy). For pair $A[i]$ and $A[j]$, the middle element is chosen at index $\lfloor\frac{i+j}2\rfloor$ in the approach above. Explain it can be chosen at index $\lceil\frac{i+j}2\rceil$ as well.

Exercise 2 (easy). Given an array of integers, find a peak in it by binary search. An array element is a peak if it is not smaller than its neighbours. An element may have 0, 1, 2 neighbourrs.

Answer 2

Lemma:

For any $i<j$, if $A[i]<A[j]$, there are certainly two neighboring elements in $A[i..j]$ such that $A[k]<A[k+1]$. Otherwise, the subarray would be non-increasing and this contradicts $A[i]<A[j]$.

Algorithm:

The dichotomy is based on the following rule:

• take $k$ to be the midpoint of $i$ and $j$;

• if $A[k]\le A[i]$, recurse on $A[k..j]$ (because $A[k]<A[j]$);

• if $A[j]\le A[k]$, recurse on $A[i..k]$ (because $A[i]<A[k]$);

• otherwise, $A[i]<A[k]<A[j]$ and you can recurse on either subarray.

---

You can also solve this in an asymmetrical but simpler way,

• if $A[k]\le A[i]$, recurse on $A[k..j]$ (because $A[k]<A[j]$);
• otherwise, recurse on $A[i..k]$ (because $A[i]<A[k]$).