patternMinor
Finding a local peak in an array in O(log N)?
Viewed 0 times
localpeaklogarrayfinding
Problem
So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the solution.
Please can someone explain it Mathematically.
Please can someone explain it Mathematically.
Solution
To reformulate the question, there is the following problem: given an array of numbers, find an index in the array that is a local maximum, meaning the value at that index $\ge$ the values at adjacent indices.
The algorithm suggested works as follows. Perform a binary search on the array. At each iteration choose a middle element of the array; examine its neighbors; if it is a local maximum or the binary search has narrowed down to just one item, output its index; otherwise recurse on a side with a greater neighbor. Clearly this algorithm runs in $O(\log n)$.
Your question is why this algorithm works.
The first observation is that every array has a local maximum. That is because an array of length 1 has a local maximum and if every array of length $n$ has a local maximum then given an array of length $n+1$, either its first element is a local maximum or each local maximum in the sub-array starting at the second element is a local maximum of the full array.
Now suppose there are two consecutive elements of the array $a, b$ and $a b$, every local maximum of the sub-array ending at $a$ is a local maximum of the full array and there must be at least one. The algorithm always recurses to one of those mentioned sub-arrays and therefore when it gets to a single-element sub-array, whose only element is a local maximum of itself, that element is also a local maximum of the sub-array in the previous step, which must be a local maximum of the sub-array two steps prior, etc., all the way back to the full array.
The algorithm suggested works as follows. Perform a binary search on the array. At each iteration choose a middle element of the array; examine its neighbors; if it is a local maximum or the binary search has narrowed down to just one item, output its index; otherwise recurse on a side with a greater neighbor. Clearly this algorithm runs in $O(\log n)$.
Your question is why this algorithm works.
The first observation is that every array has a local maximum. That is because an array of length 1 has a local maximum and if every array of length $n$ has a local maximum then given an array of length $n+1$, either its first element is a local maximum or each local maximum in the sub-array starting at the second element is a local maximum of the full array.
Now suppose there are two consecutive elements of the array $a, b$ and $a b$, every local maximum of the sub-array ending at $a$ is a local maximum of the full array and there must be at least one. The algorithm always recurses to one of those mentioned sub-arrays and therefore when it gets to a single-element sub-array, whose only element is a local maximum of itself, that element is also a local maximum of the sub-array in the previous step, which must be a local maximum of the sub-array two steps prior, etc., all the way back to the full array.
Context
StackExchange Computer Science Q#99652, answer score: 4
Revisions (0)
No revisions yet.