NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 25 题

阅读程序写结果：

#include <iostream> 
using namespace std;
int main()
{
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
cin>>a[i]; left = 1;
right = n; 
do {
middle = (left + right) / 2; 
if (f <= a[middle])
right = middle;
else
left = middle + 1; 
} while (left < right); 
cout<<left<<endl;
return 0;
}

输入： 12 17 2 4 6 9 11 15 17 18 19 20 21 25

看到二分模板 + 区间收缩 → 先想循环终止时 left==right

下标从1开始；f<=a[mid]含等号，否则目标值会被跳过

考点：二分查找｜循环控制

程序在做什么

输入 n 和 f，在已排序数组 a[1..n] 中二分查找 f 的下标。每次取中间位置，若 f<=a[mid] 则右边界缩至 mid，否则左边界缩至 mid+1，循环直到左右边界重合。