#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//search for the biggest number <= 'num'
int demo_binary_search(int A[], int n, int num)
{ printf("binary search\n"); int t=1;
int L = 0, R = n-1, mid;
while(L <= R) {
mid = (L+R) >> 1; printf(" round%d: L=%d R=%d Mid=%d A[mid]=%d%s%d\n",t++, L, R, mid, A[mid], (A[mid]<=num)?"<=":">", num);
if(A[mid] <= num) L = mid+1;
else R = mid-1;
} printf(" fin: L=%d, R=%d\n", L, R);
return R;
}
int demo_interpolation_search(int A[], int n, int num)
{ printf("interpolation search\n"); int t=1;
int L = 0, R = n-1, next;
while(L <= R) {
if(A[R] - A[L] == 0) next = R;
else next = (num*(R-L) + A[R]*L - A[L]*R) / (A[R] - A[L]);
if(next < L) next = L;
else if(next > R) next = R; printf(" round%d: L=%d R=%d Next=%d A[mid]=%d%s%d\n",t++, L, R, next, A[next], (A[next]<=num)?"<=":">", num);
if(A[next] <= num) L = next+1;
else R = next-1;
} printf(" fin: L=%d R=%d\n", L, R);
return R;
}
void fibonacci_helper(int fib[], int refib[], int n)
{
if(n > 0) fib[0] = 0;
if(n > 1) fib[1] = 1;
for(int i=2; i<n && i<50; i++)
fib[i] = fib[i-1] + fib[i-2];
for(int i=0,j=0; i<n-1 && j<n; i++)
for(; j<n && j<fib[i+1]; j++)
refib[j] = i;
if(n > 0) refib[0] = 1;
}
int demo_fibonacci_search(int A[], int n, int num)
{ printf("fibonacci search\n"); int t=1;
static int fib[1000], refib[1000];
fibonacci_helper(fib, refib, n+1);
int L = 0, R = n-1, next;
while(L <= R) {
next = fib[refib[R-L]-1] + L; printf(" round%d: L=%d R=%d Next=%d A[mid]=%d%s%d\n",t++, L, R, next, A[next], (A[next]<=num)?"<=":">", num);
if(A[next] <= num) L = next+1;
else R = next-1;
} printf(" fin: L=%d R=%d\n", L, R);
return R;
}
int main()
{
static int A[1000], N;
// array_count
// a0, a1, a2, ..., an-1
// num1, num2, ...
cin >> N;
for(int i=0; i<N; i++)
cin >> A[i];
int num;
while(cin >> num)
{
demo_binary_search(A, N, num);
demo_interpolation_search(A, N, num);
demo_fibonacci_search(A, N, num);
}
return 0;
}
