NOIP2013普及组初赛 阅读程序 第3题 《二分法》

Keywords: 二分法

分析：

这一道二分法的题目，要找一个下标，找从左往右看，第一个不小于f值的下标

测试用例和输出

代码粘上

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    freopen("erfen.in", "r", stdin);
    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 >> 1;
        if (f <= a[middle]) right = middle; //答案落在左侧；
        else left = middle + 1; 
    } while (left < right); 

    cout << left << endl;  //从左往右第一个不小于f的值的位置，注意下标从1开始 

    return 0;
}