cats 的二分答案

cats 刚刚开始学习二分答案，写出了下面这段代码（以下给出伪代码，在题目的末尾会提供 C/C++，Python，Java 语言的具体代码）



给出的数组 $a$ 下标范围为 $[1,n]$，且
$$
a_i=
\begin{cases}
1 & (i\in[1,n))\\
2 & (i=n)
\end{cases}
$$
cats 知道 $n\in[l,r]$，他希望通过以上这段代码找出 $n$ 的值。可以发现这段代码有访问越界下标的可能，访问越界下标 $i>n$ 时，会得到 $a_i=0$。但是在一次程序运行过程中，如果访问越界下标超过 $k$ 次，程序就会崩溃。现在你需要求出有多少不同的 $n$（$n\in[l,r]$）可以让程序在不崩溃的情况下得到正确结果。

第一行一个整数 $T$（$1\leq T\leq 10^3$），表示测试数据的组数。

接下来 $T$ 行，每行三个整数 $l,r,k$（$1\leq l\leq r\leq 10^{18},0\leq k\leq 10^{18}$），表示 $n$ 的范围和程序在不崩溃的情况下访问越界下标次数的上限。

对于每组测试数据，输出一个整数，表示满足条件的不同的 $n$ 的个数。

3
1 100 0
1 100 1
1 100 2

7
28
61

C/C++：
```cpp
long long BinarySearch(long long l,long long r,int *a)
{
  while(l<=r)
  {
    long long mid=(l+r)/2;
    int val=a[mid];
    if(val==2)
    {
      return mid;
    }
    if(val==1)
    {
      l=mid+1;
    }
    else
    {
      r=mid-1;
    }
  }
  return -1;
}
```
Python：
```python
def BinarySearch(l, r, a):
while l <= r:
mid = (l + r) // 2
val = a[mid]
if val == 2:
return mid
elif val == 1:
l = mid + 1
else:
r = mid - 1
return -1
```
Java：
```java
public class BinarySearch
{
public static long binarySearch(long l, long r, int[] a)
{
while(l<=r)
{
long mid=(l+r)/2;
int val=a[mid];
if(val==2)
{
return mid;
}
if(val==1)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return -1;
}
}
```

2024“钉耙编程”中国大学生算法设计超级联赛（8）