在一个整数数组中找到峰值元素的索引

在一个整数数组中找到峰值元素的索引，要求时间复杂度为 O(log n)。这可以通过二分查找实现，因为时间复杂度要求是对数级别。

代码

javaCopy codepackage org.example;

public class Main {

    public static void main(String[] args) {
        int[] nums = {1, 2, 1};
        System.out.println(findPeakElement(nums) == 1);

        int[] nums2 = {1, 2};
        System.out.println(findPeakElement(nums2) == 1);

        int[] nums3 = {1, 2, 3, 4, 5};
        System.out.println(findPeakElement(nums3) == 4);

        int[] nums4 = {4, 3, 2, 1};
        System.out.println(findPeakElement(nums4) == 0);

        int[] nums5 = {1};
        System.out.println(findPeakElement(nums5) == 0);

        int[] nums6 = {2, 1};
        System.out.println(findPeakElement(nums6) == 0);

        int[] nums7 = {1, 1};
        System.out.println(findPeakElement(nums7) == 0 || findPeakElement(nums7) == 1);

        int[] nums8 = {3, 4, 3, 2, 1};
        System.out.println(findPeakElement(nums8) == 1);
    }

    public static int findPeakElement(int[] nums) {
        return binarySearch(nums, 0, nums.length - 1);
    }

    private static int binarySearch(int[] nums, int left, int right) {
        // 当 left == right 时，找到峰值
        if (left == right) {
            return left;
        }

        // 计算中间位置
        int mid = left + (right - left) / 2;

        // 根据 mid 和 mid + 1 的比较，确定峰值方向
        if (nums[mid] > nums[mid + 1]) {
            // 峰值在左侧，包括 mid
            return binarySearch(nums, left, mid);
        } else {
            // 峰值在右侧，不包括 mid
            return binarySearch(nums, mid + 1, right);
        }
    }
}

• 当 left == right 时，直接返回 left，因为此时已经找到峰值索引。
• 通过计算中间位置 mid，根据 nums[mid] 和 nums[mid + 1] 的大小关系来确定下一个搜索的范围：
  • 如果 nums[mid] > nums[mid + 1]，则峰值在左侧（包括 mid），搜索范围缩小为 [left, mid]。
  • 如果 nums[mid] <= nums[mid + 1]，则峰值在右侧，搜索范围缩小为 [mid + 1, right]。

复杂度分析

• 时间复杂度：O(log n)，因为每次递归时，搜索范围减半。
• 空间复杂度：O(log n)，用于递归调用栈。

示例测试结果

优化后的代码通过了所有给定的测试用例，并在复杂度上满足了题目要求。