---
# System prepended metadata

title: 'd732: 二分搜尋法'

---

###### tags: Basic
 - [x] check
# d732: 二分搜尋法
:::info
在遊戲中玩家可以自由加入公會組成同盟，
已知現在有一個公會由 N 個成員組成( 1 ≤ N ≤ 500,000 )，
N 個成員的玩家編號由小到大分別為 x0, x1, ..., xN-1 ( 1 ≤ xi ≤ 1,000,000,000 )。

現在有 Q 個玩家( 1 ≤ Q ≤ 1,000,000,000 )，
請利用二分搜尋法快速確認，這 Q 個玩家是否是公會成員。
:::


```c=
#include<stdio.h>
#include<stdlib.h>
int BinarySearch(int*,int,int,int);
int main(){
    int int_length,int_quer;
    int start=0,i;
    scanf("%d%d",&int_length,&int_quer);
    int *ptr=(int*)malloc(sizeof(int)*(int_length));//declare a pointer
    for(i=0;i<=int_length-1;i++){//用一個回圈把資料讀入
        scanf("%d",&ptr[i]);
    }
    for(i=1;i<=int_quer;i++){//查詢幾次用一個回圈控制
        printf("%d",BinarySearch(ptr,start,int_length,int_quer));//做二元搜尋（剛宣告陣列的指標,起始,終止,查詢值）
    }
    
    
}
//採遞回方式
int BinarySearch(int*ptr,int start,int int_length,int int_quer){
    int min=(start+(int_length-1))/2;
    if(int_quer==min){
        return ptr[min];
    }
    else if(int_quer<min){
        return BinarySearch(ptr,start,min-1,int_quer);
    }
    else if(int_quer>min){
        return BinarySearch(ptr,min+1,int_length,int_quer);
    }
}
```