題目描述

有n個數（n<=1000000）,這n個數已按從大到小順序存放在一個數組中，然后有T次查詢，每次輸入一個數，要求用折半查找法找出該數在數組中第一次出現的位置。如果不在數組中輸出0。?

輸入

第一行數組元素的個數n

第二行n個數組元素的值?
第三行輸入查詢次數T (T<=100000)

往下有T行，每行輸入一個需要查詢的數字

輸出

查找的值在數組中的位置?

樣例輸入

10 10 9 8 7 6 5 4 3 2 1 2 9 5

樣例輸出

2 6

提示

注意：數組空間為1000000和100000

這個本來是一個原來的練習題，當時坑了好久，今天再來回味一下，這個題有很多坑點?

用cin和cout是過不了的

這個題可能有很多的重復數字，仔細看題目要求就可以得到 找到某個數第一次出現的位置，所有你找到這個數不要高興，還得往前找，此外還需要注意循環條件? left<right 不能有==

以查詢 9為例 假如加上等于號

left right mid?

1? ?10? ?5

1? ? 5? ? 3

1? ? 3? ? 2? ? 此時a[mid]<=9 ，a[mid]就是 9，right =mid =2；

1? ??2? ? ?1 此時 a[mid]=10>9; left=mid+1;

2? ? 2? ? ?2? 此時 a[mid]= 9=9; right=mid=2;

2? ? ?2? ? ?2? ? .......進入死循環 gg

#include<cstdio> using namespace std; const int maxn=1000000+10; int a[maxn],n,m,x; int getpos(int x) {int left=1;int right=n;int mid;while(left<right){mid=(left+right)/2;if(a[mid]<=x)right=mid;if(a[mid]>x)left=mid+1;}if(a[left]==x)return left;return 0; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(int i=0;i<m;i++){scanf("%d",&x);printf("%d\n",getpos(x)); } return 0; }

版本二：2020.5.16

可以用lower_bound

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <string> #include <vector> #include <stack> #include <map> #include <sstream> #include <cstring> #include <set> #include <cctype> #include <bitset> #define IO \ios::sync_with_stdio(false); \// cin.tie(0); \// cout.tie(0); using namespace std; typedef long long LL; const int maxn = 1e6 + 10; const int maxm = 1e6 + 10; const LL INF = 0x3f3f3f3f3f3f3f3f; const int inf = 0x3f3f3f3f; const LL mod = 11092019; int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1}; int a[maxn]; int n; int B_search(int val) {int L = 1;int R = n;int ans = 1;while (L <= R){int mid = (L + R) >> 1;if (a[mid] <= val)R = mid - 1;elseL = mid + 1, ans = L;}if (a[ans] != val)return 0;elsereturn ans; } bool cmp(int a, int b) {return a > b; } int main() { #ifdef ONLINE_JUDGE #elsefreopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endif// IO;int T, x;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);scanf("%d", &T);while (T--){scanf("%d", &x);printf("%d\n", B_search(x));// int p = lower_bound(a + 1, a + n + 1, x, cmp) - a;// if (a[p] == x)// printf("%d\n", p);// else// printf("0\n");}return 0; }

總結

以上是生活随笔為你收集整理的Ytu oj 折半查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。