d732 - 二分搜尋法
題目描述
題目要求給定一個嚴格遞增的數列 A 和 K 個詢問，對於每個詢問 X，在數列 A 中尋找是否存在與 X 相等的元素。如果存在，輸出該元素在數列中的索引（從 1 開始計數）；否則，輸出 0。
解題思路
題目描述中明確指出數列是嚴格遞增的，因此可以使用二分搜尋法來高效地尋找目標值。對於每個詢問，在數列 A 中執行二分搜尋，如果找到目標值，則輸出其索引加 1；否則，輸出 0。 程式碼中未使用二分搜尋法，而是使用巢狀迴圈進行線性搜尋，效率較低。
複雜度分析
- 時間複雜度: O(N*K)
- 空間複雜度: O(N+K)
程式碼
#include <iostream>
using namespace std;
int main(){
int a,b;
while(cin >> a >> b){
int c[a],d[b];
for(int i=0;i<a;i++){
scanf("%d",&c[i]);
}
for(int i=0;i<b;i++){
scanf("%d",&d[i]);
}
for(int j=0;j<b;j++){
for(int i=0;i<a;i++){
if(d[j]==c[i]){
printf("%d\n",i+1);
i=a;
}
else if(d[j]<c[i]){
printf("0\n");
i=a;
}
}
}
}
}