二分検索(intタイプ)C++バージョンpythonバージョン
6724 ワード
AcWing 789数の範囲
https://www.acwing.com/problem/content/791/
https://www.acwing.com/problem/content/791/
#include
#include
#include
using namespace std;
const int N = 1e5 + 5;
int a[N];
int x;
int binSearchLeft(int L, int R)
{
while(L < R)
{
int mid = L + R >> 1;
if(a[mid] >= x) R = mid;
else L = mid + 1;
}
if(a[L] == x)
return L;
else
return -1;
}
int binSearchRight(int L, int R)
{
while(L < R)
{
int mid = L + R + 1>> 1;
if(a[mid] <= x) L = mid;
else R = mid - 1;
}
if(a[L] == x)
return L;
else
return -1;
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i = 0; i < n; ++ i)
scanf("%d", &a[i]);
while(q --)
{
scanf("%d", &x);
int L = binSearchLeft(0, n - 1);
int R = binSearchRight(0, n - 1);
printf("%d %d
", L, R);
}
return 0;
}
n, q = map(int, input().split())
a = list(map(int, input().split()))
def binarySearchLeft(k, L, R):
while L < R:
mid = L + R >> 1
if a[mid] >= k:
R = mid
else:
L = mid + 1
if a[L] != k:
return -1
else:
return L
def binarySearchRight(k, L, R):
while L < R:
mid = L + R + 1 >> 1
if a[mid] <= k:
L = mid
else:
R = mid - 1
if a[L] != k:
return -1
return L
while q:
k = int(input())
L = binarySearchLeft(k, 0, n - 1)
R = binarySearchRight(k, 0, n - 1)
print(L, R)
q -= 1