1
$\begingroup$

Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as [0,0,0,0,1,1,1], binary search is able to find the first 1 after all the 0s in log(n) time.

Is this technique generalizable to find the index to the maximum of a unimodal boolean list with a single 1 sandwiched between 0s such as [0,0,0,0,0,1,0,0]?

It seems like any search algorithm would have trouble narrowing down the search range with all the duplicate 0s surrounding a single 1, however binary search copes well with duplicates, so I'm having trouble explaining why this is impossible.

In addition, the unimodal property required by ternary / Fibonacci search is met, where an array A with indices i < j satisfies A[i] <= A[i+1] until maximum at A[j] then A[j] >= A[j+1].

From what I've read this is possible with a list of integers, so it can't be impossible due to just discrete versus continuous functions.

What am I missing here?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Your unimodal property should be strict inequality. $\endgroup$
    – Tomoki
    Oct 4, 2017 at 0:32

1 Answer 1

Reset to default
1
$\begingroup$

No. Any algorithm for this problem requires at least $n-2$ time in the worst case. Thus, the problem requires $\Omega(n)$ time. You can't use binary search.

There's a simple adversary argument: each time the algorithm reads some index in the array, the adversary just answers 0. After the algorithm has read $n-2$ different positions in the array, there are still two possibilities for where the 1 could be, so whatever the algorithm outputs at that point is wrong for at least one input (there exists an input array that makes the algorithm wrong).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.