- Traverse the array forwards, wrapping around when you hit the end (code below)
- Count the total number of inflection points you find, if
num_inflection_points==2
then your array is bitonic.
- The runtime of this should be
O(n)
.
Here's a working example in c++:
bool is_bitonic(const vector<int>& v) {
bool was_decreasing = v.back() > v.front();
int num_inflections = 0;
for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
bool is_decreasing = v[i] > v[(i+1)%v.size()];
// Check if this element and next one are an inflection.
if (was_decreasing != is_decreasing) {
num_inflections++;
was_decreasing = is_decreasing;
}
}
return 2 == num_inflections;
}
- Notes, depending on your implementation:
Note 1: Here's the basic idea for traversing an array circularly:
for (int i = ip_index; i < array_length; i++) {
int index = (i + 1) % array_length; // wraps around to beginning
// Retrieve the value with
DoSomethingWithValue(array[index];)
}
Note 2: It might simplify the code to circularly loop length + 1
elemnts, which will guarantee you find both inflection points.
Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.
Note 4: As for your example, you can't use N/2
, because the inflection point doesn't necessarily occur at the midpoint of the array.
4 3 2 1
. You will check ifa[0] < a[1]
, which won't be true, so you'll report it's not bitonic, correct? But you can shift the array by one position to the right, obtaining1 4 3 2
, which is bitonic. So your method doesn't work. Are you looking for something faster thanO(n^2)
? I'm pretty sure I have anO(n^2)
solution.