【二分查找】山脉数组找目标值


描述

一个数字从小到大然后依次减小的数组被称为山脉数组,给定这样的一个数组,你需要在数组中查找一个数target,如果存在则输出target第一次出现的位置,否则输出-1;

解题思路

我们先通过一个修改后的二分查找函数找到山峰的位置,然后再用二分法分别查找山峰左边的数组(递增数组)和山峰右边的数组(递减数组)。

AC代码

#include<iostream>
#include<vector>
using namespace std;
int target; //要查找的数
class MountainArray{
    public :
        vector<int > arr={1,2,3,4,5,3,1}; //拟定的数组,山峰即是5所在的位置
        int length(){
            return this->arr.size();
        }
        int get(int index){
            return arr[index];
        }
}; 
class Solution{
    public :
        int findInMountainArray(int target, MountainArray &mountainArray){
            int l = 0, r = mountainArray.length()-1;
            while(l+1 < r){ //让区间逐渐逼近山峰所在的位置
                int mid = l + (r-l)/2;
                int midVal = mountainArray.get(mid);
                if(midVal>mountainArray.get(mid-1))
                l = mid;
                else r = mid;
            }
            int peakIdx = l; //找到山峰了
            int idx = search(target, 0, peakIdx, true, mountainArray); //查找山峰左边
            return idx!=-1?idx:search(target, peakIdx+1, mountainArray.length()-1, false, mountainArray); //查找山峰右边
        }
    private : 
        int search(int target, int l, int r, bool dir, MountainArray mountainArray){ //dir用于判断正在搜索的是递增数组还是递减数组
            while(l<=r){
                int mid = l + (r-l)/2;
                int midVal = mountainArray.get(mid);
                if(midVal == target) return mid; //找到数了就返回
                if(midVal<target){ //三目运算符缩短代码量
                    l = dir?mid+1:l;
                    r = dir?r:mid-1;
                }else{
                    l = dir?l:mid+1;
                    r = dir?mid-1:r;
                }
            }
            return -1;
        }
};
int main(void){
    MountainArray mountainArray; 
    Solution solution;
    cin>>target;
    cout<<solution.findInMountainArray(target, mountainArray)<<endl; //如果target是3,则会输出2
}

声明:Kira's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【二分查找】山脉数组找目标值


Truth is I missed those summer days