簡單搜尋
==

###### tags: `C++`
[總整理](https://hackmd.io/@810414/總整理)

## 二分搜尋演算法（英語：binary search algorithm）

再大量資料中，要找到(暴力搜尋)所需之資料是一間非常困難的事，
即使有了編號還是很難在龐雜資料堆中找到。

所以搜尋是必要的，以下簡單介紹二分搜。

## 原理

* 二分搜也稱折半搜尋演算法，顧名思義，將資料(已排序)不斷拆半、比較、位移直到找到。
* 舉例:
兩個人玩猜數字遊戲時(1~1000)先猜500，比較大小後如果>500則猜750,反之猜250...以此類推......
## 設定

* 資料分為左端、右端及中端，看成是當一個人再找書的時候，步行的範圍。
p.s 人會不斷走而且走過的路會知道結果，所以左端右端也會動(只找不知道結果的)。
* 以中端(陣列位置)當成拿起的書。

## 核心

* 藉著陣列指位器移動找到要的資料(陣列[]間的值是種指位器)，並節遊不斷移動邊界直到找到所求或者是重疊(代表不存在)
*

## 程式碼
1. 製造資料、目標
2. 列一個左端跟右端
3. 使用 while 迴圈 在不知道第幾次會找到，所設置的條件為 : 左端不等於右端。
4. 設置中間端，因為不知道中間段在哪，而且中間段(可想成拿起的書)會不斷變化。
5. 比較
6. 將走過的範圍移除=可走的範圍-已走的=已走的射程端點。在回到第4步驟。

int a[10]={0,1,2,3,4,5,6,7,8,9},b=3; //step 1
//現在資料跟位置值是一樣的

int left=0,right=9; // step 2

 while(left<right)
 {  //step 3 (left>right 代表無解 )
    int middle=(left+right)/2; //step 4
                
    f(a[middle]>=b)  //step 5
        right=middle;
    else left=middle+1;
 }  

# 以下待編......

## 實作
Example: (toj55 By allenwhale 2014/5/18)

鳥鳥寶貴的硬碟都快要被重複的歌曲佔滿了，於是，它用了神奇到不行的方法將電腦中擁有的歌曲編號列了出來，想要知道，它所想要下載的歌曲在電腦中是否已經存在，如果存在，它也希望知道數量，方便做清除重複檔案的工作。

* 輸入說明
第1行有一個整數N( <= 100萬)
第2行有N個數，代表已經存在於電腦中的歌曲編號 (保證可以用32-bit signed int儲存)
第3行有一個整數M( <= 100萬) ，代表鳥鳥預定要下載的歌曲數量
第4 ~ 4+M-1行每行有一個數，代表鳥鳥想要下載的歌曲編號

* 輸出說明
針對每一個鳥鳥想要下載的歌曲編號，輸出一個整數，代表該歌曲在鳥鳥電腦中存在的數量，若沒有則輸出"0" (不含雙引號)

* sample input
8
5 6 1 2 4 8 7 5
3
5
6
9

* sample output
2
1
0

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>s,q; //要不要弄個酷一點的名字?我想不到?

int main()
{
    int n1;
    cin>>n1;
    
    for(int i=0;i<n1;i++)
    {
        int a;
        cin>>a;
        s.push_back(a);
    }
    sort(s.begin(),s.end());
    
    int n2;
    cin>>n2;
    
    for(int i=0;i<n1;i++)
    {
        int a,ans;
        cin>>a;
        
        int l=s.begin(),r=s.end();
        while(l<r)
            {
                m=(l+r)/2;
                if(s[m]>=a)
                    r=m;
                else l=m+1;
            }
        
        if(s[r]==a)
        {
            for(int j=r;s[j!=s[r]];j++)
                ans=j;
        }
        cout<<ans<<'\n';
    }
}

## here

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
int N; cin>>N;
int a[N];
for(int i=0;i<N;i++){
cin>>a[i];
}
sort(a,a+N);
int k;cin>>k;
for(int i=0;i<k;i++){
int c; cin>>c; int count=0;
int left=0,right=N; int mid;
while(left<right){
mid=(left+right)/2;
if(a[mid]==c) break;
if(a[mid]>c) right=mid-1;
if(a[mid]<c) left=mid+1;
}

int ans=mid,ans2=mid-1;
while(a[ans]==c){
ans++;
count++;
}
while(a[ans2]==c){
ans2--;
count++;
}
cout<<count<<endl;
}
}