## Problem:
Given an array A[0:n] that is bitonic, there is an index 0⩽k<n, such that the slice A[0:k+1] is strictly increasing, and slice A[k:n] is strictly decreasing. We call the index k inflection point. Note that by this definition, an increasing array is bitoinic as well (with k=n-1), and a decreasing array is bitoinic (with k=0).

For example, say a Bitonic array A = [1, 3, 4, 3], then its inflection point of A, the k is 2.

Given a bitonic array A[0:n], write an algorithm (in rhythmic pseudocode) that computes the k defined above. The time complexity must be O(log n).

Note: the slice notation is like Python: left open and right closed; i.e. A[0:n] means A[0], A[1], . . . , A[n-1]. Also note that A[i:i] is empty array.

## Algorithm Description
For this problem, I use a getInflectionPoint recursive algorithm. The array is split into two halves by taking the middle index m. The algorithm compares the middle element A[m] with its right neighbor A[m+1]:
If A[m] < A[m+1], the array is still increasing, so the peak must be in the right half [m+1, j).
Otherwise, the array is falling or already at the peak, so the peak is in the left half [i, m+1), which still includes m.
This process continues until only one element remains, which is returned as the inflection (peak) point.

---

#input: bitonic array A, search window [i,j)
#output: index k of the peak point (inflection point)


fun inflectionPoint(A, i, j) {
if (j - i == 0) return null;        # base case: empty window
if (j - i == 1) return i;           # base case: exactly one element → that's the peak


var m = floor((i + j) / 2);         # compare middle with its right only 
                                    cause when j-i >= 2, m+1 <= j-1 (in bounds)

if (A[m] < A[m + 1]) {
    return inflectionPoint(A, m + 1, j)          # rising → peak is to the RIGHT
    
} else {
    return inflectionPoint(A, i, m + 1)          # falling/at peak → keep m in the window
}

## Correctness Proof

**Given.** `A` is bitonic: strictly increasing up to a unique peak `k`, then strictly decreasing.

**Goal.** `inflectionPoint(A, i, j)` returns the unique peak index `k ∈ [i, j)` when `[i, j)` is a bitonic slice containing the peak.

**Induction on window length L = j − i (numbers of elts)**

- **Base cases.**
- `L = 0`: empty window → function returns `null`.
- `L = 1`: window has a single index `i`; that element is the (unique) peak in this window → function returns `i`.

Both bases are correct.

- **Inductive step (L ≥ 2).**

Let `m = ⌊(i + j)/2⌋`. Since `L ≥ 2`, `m + 1 ≤ j − 1` is valid.

- **Case 1: `A[m] < A[m+1]`.**

The sequence is **ascending** at `m → m+1`. In a bitonic array, once you are ascending at `m`, the global peak must lie **to the right** of `m`. Hence the peak lies in `[m+1, j)`. The recursive call keeps the peak and reduces the length (< L), so by the induction hypothesis it returns the correct index.

- **Case 2: `A[m] ≥ A[m+1]`.**

The sequence is **not ascending** at `m → m+1` (falling or at the peak). Therefore the peak is **at `m` or to the left**. The subwindow `[i, m+1)` contains all indices `i … m`, including the possible peak at `m`. Again the length strictly decreases (< L), so by the induction hypothesis the recursive call returns the correct peak.

In both cases, the recursive step preserves the peak and reduces the window, so the algorithm eventually hits `L = 1` and returns that index, which is the peak.

---

## Time Complexity

- Each call does **O(1)** work.
- Each step cuts problem size about in half.
- Recurrence: `T(n) = T(n/2) + O(1)`.
- Solution: **O(log n)** time.
- Space: **O(log n)** recursive, **O(1)** iterative.