判断一个极大的数组是否是有序数组(大数据)

你的名字 2023-10-06 19:59 29阅读 0赞

## 有序数组 ##

### 判断一个极大的数组是否是有序数组 ###

***要求：时间复杂度为O(log n)***

简述算法过程：  
采用二分查找，设置一个数值，用二分查找查这个数，如果可以查到证明有序，左边数大于右边数为降序，右边数大于左边数为升序。

class Env
    {
        
    public:
        int data[40000];
        int pointer_max = 0;
        int pointer = 0;
        Env()
        {
        
            // test_3.csv test_4.csv test_5.csv   为第二题的测试用例
            ifstream file("test_data/test_1.csv", ios::in);     
            if (!file.is_open())
                cout << " 文件打开失败！" << endl;
    
            string temp;
            while (getline(file, temp))
            {
        
                data[pointer_max] = atoi(temp.c_str());
                pointer_max++;
            }
            file.close();
        }
    };
    
    // 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
    class Algo
    {
        
    public:
        Algo()
        {
        
            cout << "algo ok" << endl;
        }
    
    int osearch(int n[],int object,int m)
    {
        
        int left=0;
        int right=m;
        while(left<=right)
        {
        
            int mid=(right+left)/2;
            if(n[left]<n[mid]&&n[mid]<n[right])
            {
        
                if(n[mid]==object)
                {
        cout<<object<<"升序"<<endl;
                break;}
                else if (n[mid]<object)
                left=mid+1;
                else if (n[mid]>object)
                right=mid-1;
            }
            else{
        
                cout<<object<<"无序"<<endl;
                break;
            }
        }
    return -1;
    }
    int tsearch(int n[],int object,int m)
    {
        
        int left=0;
        int right=m;
        while(left<=right)
        {
        
            int mid=(right+left)/2;
            if(n[left]>n[mid]&&n[mid]>n[right])
            {
        
                if(n[mid]==object)
                {
        cout<<object<<"降序"<<endl;
                break;}
                else if (n[mid]<object)
                right=mid-1;
                
                else if (n[mid]>object)
                left=mid+1;
            }
            else{
        
                cout<<object<<"无序"<<endl;
                break;
            }
        }
    return -1;
    }
        int run(Env env)
        {
        
            // 在此写入你的代码
            // env.data[40000] 为已获取到的数组
            int k=150;
            int object = env.data[k];
            int left = 0;
            int right = 39999;
            int m=right;
            if(env.data[left]<env.data[right])
            osearch(env.data,object,m);
            if(env.data[left]>env.data[right])
            tsearch(env.data,object,m);
    
            return 0;
        }
    };

结果：  
![在这里插入图片描述][6abeeb03b1654077acdeb0897b3994d3.png]![在这里插入图片描述][308cb304da3d4c7b96a47038018684ac.png]

[6abeeb03b1654077acdeb0897b3994d3.png]: https://img-blog.csdnimg.cn/6abeeb03b1654077acdeb0897b3994d3.png
[308cb304da3d4c7b96a47038018684ac.png]: https://img-blog.csdnimg.cn/308cb304da3d4c7b96a47038018684ac.png