算法通关村——二分查找在寻找数组峰顶中的应用

绝地灬酷狼 2024-03-23 21:18 149阅读 0赞

## 题目 ##

> 在数组i的某个位置i 开始，从 0 到 i 都是递增的，从 i +1 都是递减的，请你找到这个最高点

### 方法一 ###

#### 使用线性遍历实现 ####

#### 分析 ####

> 最高点如果存在，需要满足arr\[i - 1\] < arr\[i\] > arr\[i + 1\] 。又因为题目说了0到i就是递增的，因此第一种办法就是只判断递减部分即可，即 i + 1 这部分。如果存在arr\[i\] > arr \[i +1\]，说明i这个下标就是最高点的下标。

#### 代码实现 ####

/**
         *在数组i的某个位置i 开始，从 0 到 i 都是递增的，从 i +1 都是递减的，请你找到这个最高点
         * 普通方法解决
         * @param arr 数组
         * @return 数组顶峰索引
         */
        public int peakIndexInMountainArray(int [] arr){
            int len = arr.length;
            // todo 不太懂
            int ans = 1;
    
            for (int i = 1; i < len-1; i++) {
                if (arr[i] > arr[i + 1]){
                    ans = i;
                    break;
                }
            }
            return ans;
        }

### 方法二 ###

#### 使用二分查找实现 ####

#### 分析 ####

> 如果要对线性遍历进行优化的话，可以考虑二分查找实现。对于二分查找的中间值mid，可能出现三种情况：
> 
> mid在递增阶段的时候，满足条件：arr\[mid\] > arr\[mid -1\]&&arr\[mid\] < arr\[mid +1\]
> 
> mid 在递减阶段的时候，满足条件：arr\[mid\] < arr\[mid -1\] && arr\[mid\] > arr\[mid +1\]
> 
> mid在顶峰的时候，满足的条件是：arr\[mid\] > arr\[mid -1\] && arr\[mid\] > arr\[mid +1\]
> 
> 因此，就可以根据mid所在的位置，调整二分查找的左右指针了。

#### 代码实现 ####

public int peakIndexInMountainArrayByFind(int [] arr){
            // 因为最少有三个值才能有顶峰的说法
            if (arr.length == 3){
                return 1;
            }
    
            int left = 1;
            int right = arr.length -2;
    
            while (left < right){
                int mid = left + ((right - left) >>1);
                // todo 理解
                // 中间值 大于左边的值  而 又大于右边的值，说明中间值是最大的，也就是顶峰，即找到了该值，将其返回
                if (arr[mid] > arr[mid-1] &&arr[mid] > arr[mid+1]){
                    return mid;
                }
                // 中间值 大于 前一个值小于后一个值，说明是单调递增的，左边部分可以忽略
                if (arr[mid] <  arr[mid+1]&& arr[mid] > arr[mid-1]){
                        left = mid +1;
                }
                // 中间值大于后一个值而小于前一个值，说明是单调递减的，右边部分可以忽略
                if (arr[mid] > arr[mid+1] && arr[mid] < arr[mid-1]){
                        right = mid - 1;
                }
            }
        return left;
        }