二分查找的概念
二分查找又稱為折半查找，主要用于查找一個有序陣列中某一個數的位置，
主要思想如下：
在一個有序陣列中，取陣列的中間值與要查找的數進行比較；
若要查找的數等于中間值，查找成功，
二分查找的步驟
若要查找的數大于中間值，則在右半區間繼續取中間值與要查找的數進行比較；
若要查找的數小于中間值，則在左半區間繼續取中間值與要查找的數進行比較；
直至最后要查找的數未出現過與中間值相等的情況，查找失敗
二分查找的優勢
二分查找因為每次查找都會把這個資料折半，所以效率相對較高，如果使用普通的查找可能會消耗太多的時間，
大家可以試試看，在1-100之間隨便設定一個數字，只需要最多最多7次肯定能猜對，每次問的都是這個數字和范圍中間的數字比大小，每次比完都能去掉一半的數字，
找某個數的位置
在有序陣列中查找某個數，找到回傳數的下標，不存在重復的值，沒有回傳-1，
【輸入描述】第一行兩個整數空格分開，分別表示序列長度n以及查詢次數m，
第二行輸出n個整數
接下來m行，每行一個整數，表示查詢的數字，
【輸出描述】輸出m行，每行為查詢數字的位置（位置從1開始算），
【樣例輸入】3 3
4 6 9
9
4
7
【樣例輸出】3
1
-1
找某個數的位置參考代碼
#include<iostream>
using namespace std;
int Search(int a[] , int n, int key){
int low = 1;
int high = n;
while(low <= high) {
int mid = low + ((high-low)/2);
if(key == a[mid]) return mid;
else if(key < a[mid])high = mid - 1;
else low = mid + 1;
}
return -1;
}
int main()
{
int s[100000],n,m,b;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=m;i++)
{
cin>>b;
cout<<Search(s,n,b)<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/1837.html
標籤：C++
上一篇：數字統計