Divide And Conquer

Find bitonic point in given bitonic sequence

A bitonic sequence is a sequence of numbers that first monotonically increases and then monotonically decreases or is entirely decreasing. A bitonic point is the maximum value in such a sequence.

To find the bitonic point in a bitonic sequence using divide and conquer, we can use the following algorithm:

Divide the sequence into two halves at the middle.
Compare the middle element with its neighbors.
If the middle element is greater than both of its neighbors, we have found the bitonic point.
If the middle element is smaller than its left neighbor, the bitonic point is in the left half of the sequence. Recursively search for the bitonic point in the left half.
If the middle element is smaller than its right neighbor, the bitonic point is in the right half of the sequence. Recursively search for the bitonic point in the right half.

Here's the Python code for the algorithm:

def find_bitonic_point(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
        return arr[mid]
    elif arr[mid] < arr[mid-1]:
        return find_bitonic_point(arr, low, mid-1)
    else:
        return find_bitonic_point(arr, mid+1, high)

The function takes the bitonic sequence arr, the lowest index low, and the highest index high as input and returns the bitonic point in the sequence. The base case of the recursion is when there is only one element in the sequence, in which case it is the bitonic point. The function then finds the middle element of the sequence and compares it with its neighbors to determine whether it is the bitonic point. If it is not, the function recursively searches for the bitonic point in either the left or the right half of the sequence, depending on the comparison.

The time complexity of the above algorithm is O(log n), where n is the length of the bitonic sequence.

Test Example

#  Python 3 program for
#  Find bitonic point in given bitonic sequence
def find_bitonic_point(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
        return arr[mid]
    elif arr[mid] < arr[mid-1]:
        return find_bitonic_point(arr, low, mid-1)
    else:
        return find_bitonic_point(arr, mid+1, high)
def main() :
	#   Bitonic sequence
	arr1 = [1, 2, 3, 4, 6, 7, 3, 2, -1]
	arr2 = [1, 10, 12, 16, 1]
	#  Test Case A
	#  [ 1 , 2, 3, 4, 6, 7, 3, 2, -1]
	#   Result = 7
	n = len(arr1)
	print(find_bitonic_point(arr1,0, n))
	#  Test Case B
	#  [ 1, 10, 12, 16,1]
	#   Result = 16
	n = len(arr2)
	print(find_bitonic_point(arr2,0, n))

if __name__ == "__main__": main()

7
16

Find bitonic point in given bitonic sequence

Test Example

Comment

New Comment