# Find bitonic point in given bitonic sequence in Python

Before finding the Bitonic point in a given Bitonic Sequence in Python, let us first understand these terms and various cases. A **Bitonic Sequence **is a sequence that is initially strictly increasing and after a point, called **Bitonic Point**, it becomes strictly decreasing. For Example, the sequence 1,4,5,7,4,2,1 is a Bitonic Sequence with 7 as it’s Bitonic Point.

Important Points:

- Increasing order Sequence is a Bitonic Sequence with an empty decreasing part. (The Last number).
- Decreasing order Sequence is a Bitonic Sequence with an empty increasing part. (First number).
- Bitonic Sequences are rotatable i.e; 2,1,4,5,6 <=> 4,5,6,2,1 is a Bitonic Sequence.

## Program to find Bitonic Point in given Bitonic Sequence in Python

To find the Bitonic point, we shall be using the modified Binary search. arr[i] is the Bitonic Point if **both** conditions satisfy

- (Condition C1) – arr[i-1] < arr[i]
- (Condition C2) – arr[i] > arr[i+1]

def search(seq, left, right): if(left == right): return right elif (left < right): mid = (left + right) // 2 if(seq[mid-1] < seq[mid] and seq[mid] > seq[mid+1]): return (mid) if(seq[mid] < seq[mid+1]): return search(seq,mid+1,right) else: return search(seq,left,mid-1) seq = list() inp = int(input("Enter the length of the sequence : ")) print("Enter the Elements of the Sequence : ") for i in range(int(inp)): e = int(input()) seq.append(e) print("Entered Sequence is : {}".format(seq)) n = len(seq) i = search(seq, 0, n-1) print("Bitonic Point is : ",seq[i])

Initially, we shall be searching among all the given list. We compare the middle element with its predecessor and successor. If the conditions satisfy, we return the mid element. If the left element is smaller than mid element (only C1 satisfy), it means the sequence is still increasing and therefore our bitonic element lies in the right half. We search in the left half if both C1 and C2 fail. If the input sequence is strictly increasing or decreasing, left and right pointers become equal at the bitonic point and we return it.

Input : [1,3,4,5,3,1] Bitonic Point is 5 Input : [1,2,3,4] Bitonic Point is 4

Thanks for reading and Keep Learning 🙂

## Leave a Reply

You must be logged in to post a comment.