# 何为二分？

``````#include
#include
using namespace std;

int main()
{
int a = rand() % 100;
cout << "请猜想你的数字" << endl;
while (1) {
int q;
cin >> q;
if (q > a) {
cout << "大了" << endl;
}
else if (q < a) {
cout << "小了" << endl;
}
else {
cout << "恭喜猜对了" << endl;
break;
}
}
return 0;
}
``````

# 例题

• 找中间值 mid = (l+r+1)/2
• if(check(mid))等于true或者是false
check(m)是检查m是在不满足性质的区间（检查是不是在棕色区间）
• 更新l或者r

• 找中间值 mid = (l+r+1)/2
• if(check(mid))等于true或者是false
check(m)是检查m是在满足性质的区间（检查是不是在红色区间）
• 更新l或者r

l=mid的情况，中间点的更新方式是m=(l+r+1)/2
r=mid的情况，中间点的更新方式是m=(l+r)/2

``````#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q, k;
int a[maxn];
int main() {
#ifndef judge
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < q; i++) {
scanf("%d", &k);
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= k) {
r = mid;  //第二种情况 找绿色区间的左端点
} else {
l = mid + 1;
}
}
if (a[l] != k) {
printf("-1 -1\n");
} else {
printf("%d ", l);
l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= k) {//第一种情况 找红色区间的右端点
l = mid;
} else {
r = mid - 1;
}
}
printf("%d\n",l);
}
}
return 0;
}

``````