Поиск ближайшего значения в отсортированном массиве

Требуется реализовать поиск в отсортированном массиве элемента, ближайшего к заданному значению. В первой строке записано одно целое число ? — размер отсортированного массива (1 <= ? <= 10^5). Далее записаны элементы массива ?? (? целых чисел, |??| <= 10^9). Затем записано целое число ? — количество запросов, которые нужно обработать (1 <= ? <= 10^5). В остальных ? строках записаны целые числа ??, определяющие запросы на поиск. Запросы нужно обрабатывать следующим образом. Для каждого числа ?? нужно найти в массиве ? такой элемент, чтобы разность между ним и ?? была минимальной. В выходной файл нужно вывести два целых числа через пробел: индекс найденного элемента и полученное минимальное расстояние. Элементы массива нумеруются индексами от 0 до ? − 1. Если ближайших элементов несколько, разрешается выводить индекс любого из них. В данной задаче ответ для каждого запроса нужно находить независимо от всех остальных запросов за время ?(log ?) в худшем случае. Как я понимаю, тут нужно идти от середины. Но я запуталась, что делать дальше. Правилен ли код? Может, можно придумать что-то более лаконичное?

#include <stdio.h>
#include <math.h>
#include <conio.h>
const int MAX_SIZE = 1000;
 
int main()
{
    int n = 0;
    int arr[MAX_SIZE] = { 0 };
    long int middle = 0;
    int closest = 0, diff = 0;
    printf("Enter the number of elements: ");
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++)
    {
        printf("Enter the element #%d: ", i+1);
        scanf_s("%d", &arr[i]);
        middle += arr[i];
    }
    middle = middle / n;
    diff = abs(middle - arr[0]);
    closest = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (abs(middle - arr[i]) < diff)
        {
            diff = abs(middle - arr[i]);
            closest = arr[i];
        }       
    }
    printf("Closest: %d\n", closest);
    getch();
    return 0;
}

UPD: Что-то получилось, но это что-то все еще не то, что нужно. Может что-то забыла добавить? Или наоборот убрать?

#include<stdio.h>
int main(){
    int N;
    scanf("%d\n", &N);
    int A[10001];
    int Y[10001];
    int index_first = 0;
    int index_last = N-1;
    for (int i=0; i<N; i++){
        scanf("%d ", &A[i]);
    }
    int Q;
    scanf("%d\n", &Q);
    for(int j=0; j<Q; j++){
        scanf("%d\n", &Y[j]);
    }
    int index_middl = index_last / 2;
for(int j=0; j<Q; j++){
    while (index_first < index_last) {
        if (Y[j] < A[index_middl]) {
            index_last = index_middl;
        } 
        else {
            index_first = index_middl;
         }
        index_middl = index_last / 2;
        if (element == array[index_middl]) 
            break;
    }
}
}