22. （阅读程序）

#include <iostream> 
using namespace std;
int a[1005],d[1005];
int find(int l, int r, int key){
    while(l<r){
        int m=(l+r)/2;
        if(a[m]>key) r=m; else l=m+1;
      }
    return r; //第9行
}
int main() 
{ 
    int n,len=1;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    d[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>=d[len]){
            len++; d[len]=a[i];
        } else{
            int j=find(1,len+1,a[i]); d[j]=a[i]; //第20行
        }
    }
    cout<<len<<endl;
    return 0;
}

（判断题）

若 a[i] 大于数组 b 中的所有元素，则第 20 行 find() 函数的返回值为 len + 1。（ ）

{{ select(1) }}

• 对
• 错

将第 9 行代码 “return r;” 改为 “return l;”，不影响程序的运行结果。（ ）

{{ select(2) }}

• 对
• 错

（选择题）

该程序的时间复杂度为（ ）

{{ select(3) }}

• O(log₂n)
• O(n)
• O(nlog₂n)
• O(n²)

输入：

20

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

输出（ ）

{{ select(4) }}

• 5
• 6
• 7
• 8