Given a bitonic array find the maximum value of the array. An array is said to be bitonic if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers
belongs to collection: Interview C++ coding problems/challenges |searching
All Answers
total answers (1)
Definitely the brute force solution even works in linear time where you just pick each element and compare with the previous & next element. That’s pretty simple. But the concept of bitonic search leads up to more optimized solution reducing the number of comparison.
Algorithm:
Pre-requisite:
Bitonic array, low index (lower bound), high index (upper bound)
Time complexity: O(log(n))
C++ implementation
Output
Explanation with example:
So, in this input case we only need one comparison, where if we had done in brute force, would have required 3 comparisons.
need an explanation for this answer? contact us directly to get an explanation for this answer