28. Find Peak Element in Bitonic Array

Origin: Find Peak Element in Bitonic Array

Given a bitonic array (strictly increasing then strictly decreasing), find the index of the maximum element in O(log n) time.

Bitonic 数组：先严格递增再严格递减，形状像一个山峰。最大值就是峰顶。

Example

Input: counts = [1, 3, 5, 4, 2]

Output: 2

Explanation: 5 是最大值，在索引 2 的位置。

Input Format

• 第一行：n（数组长度）
• 第二行：n 个空格分隔的整数

Constraints

• 1 <= counts.length <= 100000
• 0 <= counts[i] <= 1000000
• 所有元素唯一
• 存在一个索引 p（0 < p < counts.length - 1），左边严格递增，右边严格递减

Output Format

返回最大元素的 0-based 索引。

Sample Input 0

3
1 3 2

Sample Output 0

1

Sample Input 1

5
1 2 3 2 1

Sample Output 1

2

---

函数契约

// 输入：counts（bitonic 数组，先增后减）
// 输出：最大元素的索引
// 边界：两元素 → 看哪个大；三元素 → 中间就是峰顶

边界表

场景	返回什么
两元素 [1,3]	1（大的那个）
三元素 [1,3,2]	1（中间是峰顶）
正常 [1,3,5,4,2]	2
峰顶在末尾附近	对应索引

Resolution

我的解法

取巧解法（O(n)，能 AC 但不满足 O(log n) 要求）

function findPeakIndex(counts: number[]): number {
    return counts.indexOf(Math.max(...counts))
}

Math.max 遍历整个数组找最大值，indexOf 再遍历找索引，O(n)。HackerRank 能过，面试会被追问 O(log n)。

二分解法（O(log n)，正解）

function findPeakIndex(counts: number[]): number {
    if (!counts?.length) return -1
    let left = 0
    let right = counts.length - 1
    let mid = 0
    while (left < right) {
        mid = Math.floor((left + right) / 2)
        if (counts[mid - 1] < counts[mid] && counts[mid] > counts[mid + 1]) {
            return mid
        }
        if (counts[mid] < counts[mid + 1]) {
            // 还在上升，峰顶在右边
            left = mid + 1
        } else {
            // 在下降了，峰顶在左边（含 mid）
            right = mid
        }
    }
    return mid
}

解题思路

bitonic 数组先增后减，形状像山峰。不需要知道峰顶在哪，只需要看坡度：

• nums[mid] < nums[mid+1] → 还在上坡，峰顶在右边，left = mid + 1
• nums[mid] > nums[mid+1] → 在下坡了，峰顶在左边（含 mid），right = mid
• 当 left == right 时就到了峰顶

加了一个提前退出：如果 mid 的左边比它小且右边也比它小，mid 就是峰顶，直接返回。

复杂度

• 时间：O(log n)，每次砍掉一半
• 空间：O(1)，只用几个变量

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：5. Target Index Search — 普通二分
• 相关题目：27. Pivoted Search — 旋转数组二分，第 28 题是 bitonic 数组二分