Writing an algorithm which takes $O(\log n)$ to run

Question

there was a question in the exam as below:

Let we have a sorted array consisting of $n$-many positive integers. Write a code that checks whether $k^{th}$ term is $k$ or not which takes $O(\log n)$ to run.

Even if I know that it will take much more time than $O(\log n)$, I wrote a code in Magma CAS language. First, I said that the array we have is $A$ and created a new array $B$ such that $B[i]=A[i]-i$. Then for $i \in {1,\dots, n}$ I run the code to check whether $B[i]==0$ or not.

How can we write such a code with computing time $O(\log n)$? Thanks.

Answer 1

If you are allowed to have the same number appear multiple times (necessarily consecutively) in the array, then it's impossible to do in $O(\log n)$ time.

Hint: I am assuming the same number cannot appear twice, and that what you want your algorithm to check is "is A[k] == k for all k?"

Then see what you can get out of the fact that the array is a sorted array containing only positive numbers, and think about how $O(\log n)$ algorithms usually work: By repeatedly splitting in half and discarding one part. Also, forget your B array, as simply creating it takes $O(n)$ time.

Answer 2

It can be done in $\mathcal{O}(1)$.
In C++ language:

#include <iostream>
using namespace std;
// int A[size]
// Assume we already have the sorted array A
int main(){
    int k;
    cin >> k;
    if(A[k] == k){
        cout << "True" << endl;
    }else{
        cout << "False" << endl;
    }
    return 0;
}

But if you meant $\Theta(\log{n})$.

#include <iostream>
using namespace std;
// int A[size]
// Assume we already have the sorted array A
int main(){
    int k;
    cin >> k;
    int idx1 = lower_bound(A,A+size,k)-A;
    int idx2 = upper_bound(A,A+size,k)-A;
    if(idx1 <= k && k < idx2){
        cout << "True" << endl;
    }else{
        cout << "False" << endl;
    }
    return 0;
}

The latter code uses binary search algorithm which takes averagely logarithmic time.