1
$\begingroup$

Suppose $A$ is an array of distinct natural numbers. We call an element $A[i]$ minimal if it's less than both the element before and after it (if any). Present a worst-case $O(\log n)$ algorithm for finding a minimal element. I wanted to find the minimum (since it's less than all the elements) and then use binary search with it as a key but you can't find minimum in logarithmic time. My other idea was to categorize the elements into three-element groups but it doesn't work as well. We should probably solve this question with divide and conquer approach.

$\endgroup$
1
$\begingroup$

You can do a "sort-of" binary search to find such an item.

  • When $A[i]\le A[i-1]$, go "forward" in the search (increment the left pointer)
  • When $A[i] > A[i-1]$, go "backward" in the search (decrement the right pointer)
$\endgroup$
2
  • $\begingroup$ But if we start from the middle and follow such a procedure and if the right half elements are decreasing then we'll be doing a linear number of comparisons, not logarithmic. Right? Maybe I didn't understand what you said well or I made a mistake. $\endgroup$
    – Emad
    Aug 21 '21 at 16:19
  • 1
    $\begingroup$ the "increment" or "decrement" operations means to take either the right or the left pointers (lets call the pointer we do the operation on $p$) and do $p \leftarrow i$, just as you would in a normal binary search. Its easy to understand why this is logarithmic (it is for the same reason that binary search is), but it is more tricky to understand why this procedure returns a correct answer. Try to prove it for yourself :) $\endgroup$
    – nir shahar
    Aug 21 '21 at 16:33
0
$\begingroup$

Your problem is equivalent to 1D Peak Finding, check this link, that use binary search approach to find a peak (if exists).

Note that, in your idea, because of you search for minimum element, the running time will be $\Omega(n)$, but you can solve your problem in $\mathcal{O}(\log n)$.

$\endgroup$

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.