2022.11.19 AM 11:50 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=d732 出題者 : PCSHIC 標籤 : 二分搜尋法 難易度 : 3
解題想法 : 題目已經保證由小到大,因此假如有個數字a在數列中,則比a左邊的不可能有數字比a大,反之比a右邊的不可能有數字比a小,根據此規則就可以每次都縮小搜尋範圍。 實作上則是先定義好L和R(左右界),並每次檢查M=(L+R)/2的位置的值,若為目標則直接return M,否則若M比目標大則不需要搜尋比M更大的部分(不可能會是解),所以右界就直接設定為M,反之則設定左界為M,若連while()結束都還沒return表示沒找到,則回傳-1。 題目問的「位置」是從1開始算,所以輸出時要再+1,這也是為什麼搜尋時如果沒找到要return -1的原因。
//C language
//solution link(含註解):
#include<stdio.h>
#define MAXN 100005
#define MAXK 100005
int n,k,data[MAXN],Q[MAXK];
int binarysearch(int target){
int L=-1,R=n;
while(R-L>1){
int M=(L+R)/2;
if(data[M]==target) return M;
if(data[M]>target) R=M;
else L=M;
}
return -1;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&data[i]);
}
for(int i=0;i<n;i++){
int a;
scanf("%d",&a);
printf("%d\n",binarysearch(a)+1);
}
return 0;
}

//C++ language
//solution link(含註解):
#include<iostream>
using namespace std;
int main(){
cin>>n>>k;
int a;
for(int i=0;i<n;i++){
cin>>a;
data.push_back(a);
}
for(int i=0;i<n;i++){
cin>>a;
cout<<binarysearch(a)+1<<"\n";
}
return 0;
}

## Python language
## solution link(含註解):
n,k=map(int,input().split())
data=[int(x) for x in input().split()]
Q=[int(x) for x in input().split()]
def binarysearch(target):
L=-1; R=n
while R-L>1:
M=(L+R)//2
if data[M]==target: return M
if data[M]>target: R=M
else: L=M
return -1
for i in Q: print(binarysearch(i)+1)

發佈留言