LeetCode 1095. 山脉数组中查找目标值

Categories:

题目描述
思路分析
1. 解法一：三次二分（找峰顶 + 两段搜索）（推荐）
相似题目

题目描述

✅ 1095. 山脉数组中查找目标值

思路分析

解法一：三次二分（找峰顶 + 两段搜索）（推荐）

核心思路：

先用二分查找峰顶下标 peak。

在 [0, peak] 递增段二分查找目标。

若未找到，再在 [peak+1, n-1] 递减段二分查找目标。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)。

// 三次二分：找峰顶 + 两段搜索
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int peak = findPeak(mountainArr, 0, n - 1);

        int left = binarySearchAsc(mountainArr, 0, peak, target);
        if (left != -1) {
            return left;
        }
        return binarySearchDesc(mountainArr, peak + 1, n - 1, target);
    }

    private int findPeak(MountainArray arr, int left, int right) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int binarySearchAsc(MountainArray arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = arr.get(mid);
            if (val == target) {
                return mid;
            }
            if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    private int binarySearchDesc(MountainArray arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = arr.get(mid);
            if (val == target) {
                return mid;
            }
            if (val < target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

// 三次二分：找峰顶 + 两段搜索
func findInMountainArray(target int, mountainArr *MountainArray) int {
	n := mountainArr.Length()
	peak := findPeak(mountainArr, 0, n-1)

	idx := binarySearchAsc(mountainArr, 0, peak, target)
	if idx != -1 {
		return idx
	}
	return binarySearchDesc(mountainArr, peak+1, n-1, target)
}

func findPeak(arr *MountainArray, left, right int) int {
	for left < right {
		mid := left + (right-left)/2
		if arr.Get(mid) < arr.Get(mid+1) {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

func binarySearchAsc(arr *MountainArray, left, right, target int) int {
	for left <= right {
		mid := left + (right-left)/2
		val := arr.Get(mid)
		if val == target {
			return mid
		}
		if val < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func binarySearchDesc(arr *MountainArray, left, right, target int) int {
	for left <= right {
		mid := left + (right-left)/2
		val := arr.Get(mid)
		if val == target {
			return mid
		}
		if val < target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

相似题目

题目	难度	考察点
852. 山脉数组的峰顶索引	简单	二分查找
162. 寻找峰值	中等	二分查找
33. 搜索旋转排序数组	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
704. 二分查找	简单	二分查找
540. 有序数组中的单一元素	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/33128240