六周"/>
hiho第三十六周
二分查找1.利用STL的lower_bound
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int a[maxn];
int main()
{int n, k;scanf( "%d%d", &n, &k);for ( int i = 0; i < n; i++){scanf( "%d", &a[i]);}sort( a, a + n);int * x = lower_bound( a, a + n, k);if ( *x == k)printf( "%d\n", x - a + 1);elseprintf( "-1\n");return 0;
}
2.直接写二分
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int a[maxn];
int main()
{int n, k;scanf( "%d%d", &n, &k);for ( int i = 0; i < n; i++)scanf( "%d", &a[i]);sort( a, a + n);int x = 0, y = n - 1, mid;while ( x <= y){mid = ( x + y) / 2;if ( a[mid] == k)break;else if ( a[mid] > k)y = mid - 1;else if ( a[mid] < k)x = mid + 1;}if ( x <= y)printf( "%d\n", mid + 1);elseprintf( "-1\n");return 0;
}
更多推荐
hiho第三十六周
发布评论