What is a bitonic sequence?
Bitonic sequence
A bitonic sequence is a sequence of numbers in which, at first, the numbers are in increasing order, and after a certain point, they start decreasing.
Example
The sequence
Types of bitonic sequences
A bitonic subsequence can be of the following three types:
It can consist of numbers that are first increasing and then decreasing. For example,
. It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example,
. It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example,
.
Example
Let's implement the code to find if the given sequence is a bitonic sequence.
#include <iostream>using namespace std;// Helper function to print sequencevoid printSequence(int arr[], int n){string out = "[";for (int i = 0; i < n; i++){out+= to_string(arr[i]) + ", ";}out = out.substr(0, out.length() -2);out += "]";cout << out << endl;}// Finding index of maximum value in an arrayint find_maxIndex(int arr[], int n){int max_index = 0;for (int i = 1; i < n; i++){if (arr[i] > arr[max_index]){max_index = i;}}return max_index;}bool isIncreasingBitonic(int arr[], int low, int high){//Base caseif (high == low){return true;}// Checking for the non increasing pair in arrayif (arr[high] < arr[high - 1]){return false;}return isIncreasingBitonic(arr, low, high - 1);}bool isDecreasingBitonic(int arr[], int low, int high){// Base caseif (high == low){return true;}// Checking for the non decreasing in arrayif (arr[high] > arr[high - 1]){return false;}return isDecreasingBitonic(arr, low, high - 1);}bool isBitonic(int arr[], int n, int max_index){// If array is the increasing bitonic// then the maximum element will be at the last indexif(max_index == n){return isIncreasingBitonic(arr,0,n);}// If array is the decreasing bitonic// then the maximum element will be at the 0th indexelse if(max_index == 0){return isDecreasingBitonic(arr,0,n);}// If array is first increasing and then decreasing bitonic// First check for increasing bitonic till max value// Then check for decreasing bitonic from max value till end of arrayelse{return isIncreasingBitonic(arr,0,max_index) && isDecreasingBitonic(arr,max_index,n);}}int main(){int arr[] = {2, 3, 7, 9, 15, 10, 4};int n = sizeof(arr) / sizeof(arr[0]);// Finding index for maximum elementint max_index = find_maxIndex(arr,n);//Printing sequencecout << "The sequence is: ";printSequence(arr, n);// Checking if the array is bitonicif (isBitonic(arr, n-1, max_index)){cout << "This is a bitonic sequence." << endl;}else{cout << "This is not a bitonic sequence." << endl;}return 0;}
Explanation
Lines 5–14: We defined the
printSequence()method to print the sequence.Lines 17–26: We defined the
find_maxIndex()method to find the index of the maximum value in the sequence.Lines 28–40: We defined the recursive method
isIncreasingBitonic()to find if the array is an increasing bitonic sequence.Lines 42–54: We defined the recursive method
isDecreasingBitonic()to find if the array is a decreasing bitonic sequence.Lines 56–73: We write the
isBitonic()method which uses theisIncreasingBitonic()andisDecreasingBitonic()method to find if the given sequence is a bitonic sequence or not.
Free Resources