2022 年 11 月 19 日

C, C++, Python, ZJ解題

d732: 二分搜尋法

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)

相關文章

發佈留言取消回覆