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 🙂

Also Read:  How to call a function in Python using Node.js

Leave a Reply

Your email address will not be published. Required fields are marked *