The program fragment below performs binary search of an integer
number in an array that is sorted in a nondescending order:
Pascal
procedure BinarySearch(x: integer; N: integer; A: array of integer);
var
p, q, i, L: integer;
begin
p := 0; { Left border of the search }
q := N  1; { Right border of the search }
L := 0; { Comparison counter }
while p <= q do begin
i := (p + q) div 2;
inc(L);
if A[i] = x then begin
writeln('Found item i = ', i, ' in L = ', L, ' comparisons');
exit
end;
if x < A[i] then
q := i  1
else
p := i + 1
end
end;
C++
void BinarySearch(int x, int N, int* A)
{
int p = 0; // Left border of the search
int q = N  1; // Right border of the search
int L = 0; // Comparison counter
while (p <= q) {
int i = (p + q) / 2;
++L;
if (A[i] == x) {
printf("Found item i = %d in L = %d comparisons\n", i, L);
return;
}
if (x < A[i])
q = i  1;
else
p = i + 1;
}
}
Python
def BinarySearch(x: int, N: int, A: list):
p = 0 # Left border of the search
q = N  1 # Right border of the search
L = 0 # Comparison counter
while p <= q:
i = (p + q) // 2
L += 1
if A[i] == x:
print('Found item i =', i, 'in L =', L, 'comparisons')
return
if x < A[i]:
q = i  1
else:
p = i + 1
Before BinarySearch was called, N was set to some integer number from 1 to 10000 inclusive and
array A was filled with a nondescending integer sequence of length N.
It is known that the procedure has terminated with the message
"Found item i = XXX in L = XXX comparisons" with some
known values of i and L.
Your task is to write a program that finds all possible values of
N that could lead to such message. However, the number of
possible values of N can be quite big. Thus, you are asked to group all
consecutive values of N into intervals and write down only first and
last value in each interval.
Input
The input consists of a single line with two integers i
and L (0 ≤ i ≤ 9999;
1 ≤ L ≤ 14), separated by a space.
Output
On the first line of the output write the single integer number K
representing the total number of intervals for possible values of N.
Then K lines shall follow listing those intervals in an ascending order.
Each line shall contain two integers A_{i} and B_{i}
(A_{i} ≤ B_{i})
separated by a space, representing first and last value of the interval.
If there are no possible values of N exist, then the output shall contain the single 0.
Samples
input  output 

9000 2
 0

10 3
 4
12 12
17 18
29 30
87 94

Problem Source: 20002001 ACM Northeastern European Regional Programming Contest