Tony041010

贓車查緝(Binary Sarch 二分搜尋法)

Dec 24th, 2020
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.     int piece,piece2;
  5.     string check_number;
  6.     cin>>piece;
  7.     string list[piece];
  8.     for(int i=0;i<piece;i++){
  9.         cin>>list[i];
  10.     }
  11.     sort(list,list+piece);
  12.     cin>>piece2;
  13.     for(int q=0;q<piece2;q++){
  14.         cin>>check_number;
  15.        
  16.         //二分搜尋法實作
  17.         int found =0;
  18.         int L=0,R=piece-1,M;
  19.         while(L<=R){
  20.             M=int((L+R)/2);
  21.             if(list[M]==check_number){
  22.                 found =1;
  23.                 break;}
  24.             else if(list[M]>check_number){
  25.                 R=M-1;}
  26.             else{L=M+1;}
  27.         }
  28.         if(found==1) cout<<"Y\n";
  29.         else cout<<"N\n";
  30.     }
  31.    
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment