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

点击量: 725 次

描述

一个数字从小到大然后依次减小的数组被称为山脉数组,给定这样的一个数组,你需要在数组中查找一个数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
}
IDEA配置tomcat运行Servlet教程 
下一篇:IDEA配置tomcat运行Servlet教程


点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出

已有 5 条评论


  1. zgcwkj
    zgcwkj

    证书过期了~

     回复
    1. Kira
      Kira

      是的,有没有免费的证书推荐

       回复
      1. zgcwkj
        zgcwkj

        网上有一年一次,免费的~ huaji.png

         回复
  2. 2broear
    2broear

    kira好久没更新了

     回复
    1. Kira
      Kira

      啊哈哈是啊,不知道写什么好。

       回复

pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2020 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信