Problem Statement

Given a Bitonic array, find if a given key is present in it. An array is considered bitonic if it is first strictly increasing and then strictly decreasing.

In other words, a bitonic array starts with a sequence of increasing elements, reaches a peak element, and then follows with a sequence of decreasing elements. The peak element is the maximum value in the array.

Write a function to return the index of the key. If the 'key' appears more than once, return the smaller index. If the key is not present, return -1.

Example 1:

Input: [1, 3, 8, 4, 3], key=4
Output: 3

Example 2:

Input: [3, 8, 3, 1], key=8
Output: 1

Example 3:

Input: [1, 3, 8, 12], key=12
Output: 3

Example 4:

Input: [10, 9, 8], key=10
Output: 0

Constraints:

• 1 <= arr.length <= 10⁵
• -10⁵ <= arr[i], key <= 10⁵
• No two neighbours are equal, so arr[i] != arr[i + 1] for every valid i.
• Either slope may be empty. An array that only rises, or only falls, is still bitonic.