Найдите номер, который удовлетворяет ограничениям

Question

У меня есть два номера P и K. У меня есть массив A из N integers.I хочу найти наименьшее число A[i], который просто удовлетворяет свойства abs(A[i]-P) <= K где 0 <= i < N. Показано, что A сортируется.

Первоначально, я думал о O(N) подхода. Но я думаю, что его можно оптимизировать до O(logN), используя двоичный поиск. Но я не знаю, как двигаться дальше.

Answer 1

Используйте это:

for(i=0; i<=n; i++)pre[i]=0; 
    for(i=1; i<=n; i++) 
    { 
      pre[i]=pre[i-1]; 
      if(s[i-1]=='1')pre[i]++; 
    } 
    for(i=1; i<=n; i++) 
    { 
      if(s[i-1]=='0')continue; 
      ans += pre[min(n,i+k)]-pre[max(0ll,i-k-1)]; 
    } 
    LL gc=gcd(ans,n*n); 
    cout << ans/gc << "/" << (n*n)/gc << endl; 

Answer 2

Try следующая логика:

• Найти минимальный номер индекс, который >= abs(P-K) с помощью двоичного поиска, если не найден идти дальше,
• Найти минимальный индекс номер, который <= (P+K) используя двоичный поиск, если не найден, то такого числа нет.

Это O(log(n)) думаю.