题目描述 下面的图形是著名的杨辉三角形： 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯ 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？ 输入描述 输入一个整数 NN。 输出描述 输出一个整数代表答案。

算法1 数学

数列中的数可以通过组合数来计算：第 n 行第 k 个数为 C(n-1, k-1)。因此可以按顺序计算数列中每个数，直到第一个大于等于 N 的数出现为止。

时间复杂度：O(N^2)

C++ 代码

算法2 二分查找

观察数列，可以发现它是逐行递增的，因此可以考虑使用二分查找。具体地，在数列中找到第一个大于等于 N 的数。至于如何找到第 n 行第 k 个数，可以使用公式 C(n-1, k-1)，也可以使用递推式 C(n, k)=C(n-1, k-1)+C(n-1, k)来计算。

时间复杂度：O(log^2 N)

C++ 代码