```cpp // https://dashoj.com/p/88 #include <bits/stdc++.h> #define N 100010 using namespace std; int n, q, x; vector<int> ls(N, 0); int main() { cin >> n >> q; for (int i = 0; i < n; i++) cin >> ls[i]; while (q--) { cin >> x; int l = 0, r = n - 1, ans = 0; while (l <= r) { int m = (l + r) >> 1; if (ls[m] >= x) { ans = m; r = m - 1; } else l = m + 1; } if (ls[ans] == x) cout << ans << ' '; else { cout << "-1 -1" << endl; continue; } l = 0, r = n - 1, ans = 0; while (l <= r) { int m = (l + r) >> 1; if (ls[m] <= x) { ans = m; l = m + 1; } else r = m - 1; } cout << ans << endl; } return 0; } ```

万能二分板子，找左右边界即可 PS:记得注意下标嗷 ```c++ #include <bits/stdc++.h> #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f const int N = 100010; using namespace std; int arr[N]; int n,q,tmp; int bs_left(int arr[],int n,int x){ int l = 0; int r = n+1; while(l+1<r){ int mid = (l+r)/2; if(arr[mid]<x){ l = mid; }else{ r = mid; } } if(arr[r] == x){ return r-1; }else{ return -1; } } int bs_right(int arr[],int n,int x){ int l = 0; int r = n+1; while(l+1<r){ int mid = (l+r)/2; if(arr[mid]<=x){ l = mid; }else{ r = mid; } } if(arr[l] == x){ return l-1; }else{ return -1; } } signed main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i = 1; i<= n;i++){ cin>>arr[i]; } while(q--){ cin>>tmp; int ans_left = bs_left(arr,n,tmp); int ans_right = bs_right(arr,n,tmp); cout<<ans_left<<" "<<ans_right<<endl; } return 0; } ```

include using namespace std; define int long long int a[100005],n,q,i,x,j,h; int check(int m,int l,int r) { if(l>r) return -1; int mid=(l+r)/2; if(m==a[mid]) return mid; else if(m >n>>q; for(i=0;i >a[i]; for(i=0;i >x; int t=check(x,0,n-1); if(t>=0) { for(j=t+1;j =0;h--) { if(a[h]!=a[t]) break; } cout<<h+1<<' '<<j-1<<endl; } else cout<<-1<<' '<<-1<<endl; } return 0; }

include using namespace std; const int N = 1e5 + 10; int a[N]; int n, q; int main() { cin.tie(0); cout.tie(0); ``` cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i]; } while (q--) { int x; cin >> x; int l = 1, r = n; int ans; while (l <= r) { int mid = (l + r) / 2; if (a[mid] >= x) { ans = mid; r = mid - 1; } else { l = mid + 1; } } if (a[ans] != x) { cout << "-1 -1" << endl; continue; } cout << ans - 1 << " "; l = 1, r = n, ans = 1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] <= x) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans - 1 << endl; } return 0; ``` }

Python调库 ```python import sys import bisect input = sys.stdin.readline n, q = map(int, input().split()) d = list(map(int, input().split())) for _ in range(q): num = int(input()) if num < d[0] or num > d[-1]: print(-1, -1) continue left = bisect.bisect_left(d, num) if d[left] != num: print(-1,-1) continue right = min(bisect.bisect_right(d, num), n-1) if d[right] != num: right-=1 print(left,right) ```

include #include using namespace std; pair findRange(const vector & arr, int target) { int n = arr.size(); int left = -1, right = -1; ``` // 寻找起始位置 int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else if (arr[mid] > target) { high = mid - 1; } else { left = mid; high = mid - 1; // 继续寻找左边界 } } // 寻找终止位置 low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else if (arr[mid] > target) { high = mid - 1; } else { right = mid; low = mid + 1; // 继续寻找右边界 } } return {left, right}; ``` } int main() { int n, q; cin >> n >> q; ``` vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } for (int i = 0; i < q; ++i) { int target; cin >> target; pair<int, int> result = findRange(arr, target); cout << result.first << " " << result.second << endl; } return 0; ``` }

用python做的,前面一部分判断在最左边和最右边的情况，然后分析不在边界的情况，用二分法找到其中一个值的时候，再用循环分别向前找和向后找并记录位置 ``` n,q = map(int,input().split()) num_list = list(map(int,input().split())) quest_list=[] def check(num): global num_list begin = 0 end = len(num_list) - 1 pos_begin = 0 pos_end = 0 flag = True if num_list[begin] == num: flag = False count = 0 pos_begin = 0 while (num_list[count] == num): pos_end = count count += 1 elif num_list[end] == num: flag = False count = len(num_list) - 1 pos_end = len(num_list) - 1 while (num_list[count] == num): pos_begin = count count -= 1 else: while((end - begin) != 1): middle = (begin + end) // 2 if num > num_list[middle]: begin = middle elif num <num_list[middle]: end = middle else: flag = False count1 = middle count2 = middle while(num_list[count1] == num): pos_begin = count1 count1 -= 1 while(num_list[count2] == num): pos_end = count2 count2 += 1 break if flag: pos_begin = -1 pos_end = -1 print(pos_begin,pos_end) for i in range(q): quest_list.append(int(input())) for quest_num in quest_list: check(quest_num) ```

一种全新的思路来解决二分问题 不需要仔细思考边界问题 ``` #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<string> using namespace std; int n,q; const int N=100010; int nums[N]; int front_find(int target){ int l=-1,r=n; while(l+1!=r){ int mid=l+r>>1; if(nums[mid]<target) l=mid; else r=mid; } if(r==n || nums[r]!=target) return -1; else return r; } int end_fond(int target){ int l=-1,r=n; while(l+1!=r){ int mid=l+r>>1; if(nums[mid]>target) r=mid; else l=mid; } if(l==-1 || nums[l]!=target) return -1; else return l; } void slove(){ int target; cin>>target; int l=front_find(target); if(l!=-1){ int r=end_fond(target); cout<<l<<" "<<r<<endl; } else cout<<"-1 -1"<<endl; } int main(){ cin>>n>>q; for(int i=0;i<n;i++) scanf("%d",&nums[i]); while(q--) slove(); return 0; } ```

``` #include <bits/stdc++.h> #define endl '\n' using namespace std; typedef pair<int,int> PII; using ll = long long; using ULL = unsigned long long; const int N = 1e6+5; int n, q; int a[N]; inline void solve() { cin >> n >> q; for (int i = 0; i < n; i++) cin >> a[i]; for (; q-- ;) { int x; cin >> x; int l = 0 ,r = n - 1; while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x) r = mid; else l = mid + 1; } if (a[l] != x) cout << "-1 -1" << endl; else { cout << l << ' '; int l = 0, r = n - 1; while (l < r) { int mid = (l + r + 1) >> 1; if (a[mid] <= x) l = mid; else r = mid - 1; } cout << l << endl; } } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //int _; cin >> _; while (_--) solve(); return 0; } ```

``` #include<bits/stdc++.h> using namespace std; const int N=100010; int arr[N]; int n,q,tmp; int bs_left(int arr[],int n,int x) { int l=0,r=n+1; while(l+1<r) { int mid=(l+r)/2; if(arr[mid]>=x)//x——正无穷，只能从第一个等于x退出，从右向左往x挤 { r=mid;//在最终检查时，如果 arr[mid] == x，说明 r 正好指向第一个出现 x 的位置 } else { l=mid; } } if(arr[r]==x) { return r-1; } else { return -1; } } int bs_right(int arr[],int n,int x) { int l=0,r=n+1; while(l+1<r) { int mid=(l+r)/2; if(arr[mid]<=x)//负无穷——x，只能从最后一个x退出，从左向右往x挤 { l=mid;//在最终检查时，如果 arr[mid] == x，说明 l 正好指向最后一个出现 x 的位置 } else { r=mid; } } if(arr[l]==x) { return l-1; } else { return -1; } } int main() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>arr[i]; } while(q--) { cin>>tmp; int ans_left=bs_left(arr,n,tmp); int ans_right=bs_right(arr,n,tmp); cout<<ans_left<<" "<<ans_right<<endl; } return 0; } ```