2
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ This explanation is awesome, so when we really check if an element is less than the $A[n-1]$ element, we have a new candidate for our $A[0]$, and when the opposite we have a new candidate for $A[n-1]$, if I wanted to proof it with a loop invariant, I could try writing: "At the start of every iteration, $A[l...r]$ contains a pair that satisfy the requirements if such a pair exists in the array" where $l,r$ would be updated just how you wrote, and then I can use the logic that I stated, if $A[m]$ (middle) is lower than the end, then there must be a pair at right side, else left side, but what $\endgroup$
    – Pwaol
    May 5 at 18:51
  • 2
    $\begingroup$ @JohnL - assuming the elements are fully ordered. Otherwise consider [0.1, NaN, 0.2]. $\endgroup$
    – TLW
    May 6 at 1:32
5
$\begingroup$

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]$).
$\endgroup$
3
  • 1
    $\begingroup$ ...assuming the elements are fully ordered. Otherwise consider [0.1, NaN, 0.2]. $\endgroup$
    – TLW
    May 6 at 1:33
  • 1
    $\begingroup$ @TLW: the standard computational models have no notion of NaNs, this is not relevant. $\endgroup$ May 6 at 6:35
  • $\begingroup$ @YvesDaoust Thanks alot! $\endgroup$
    – Pwaol
    May 6 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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