edited by
740 views
1 votes
1 votes

Given a sorted array of distinct integer $A\left [ 1,2,....n \right ]$, the tightest upper bound to check the existence of any index $i$, for which $A[i]=i$ is equal to _______________


I thought here answer that mean time complexity will be $O(1),$ because directly getting the searching index and then checking if $A[i]=i$, but answer given as $O(log n).$Please help me out, which will be correct answer?

edited by

1 Answer

0 votes
0 votes
using binary search it will take O(logn)

mid=low+high/2

compare      (key > mid)

                 mid+1,high

                     (key<mid)

                low, mid-1

Related questions

0 votes
0 votes
1 answer
3
srestha asked Apr 20, 2019
590 views
for(k=1;k<(n+1);k++) { for(m=1;m<(n+1);m+=k){ x=x+1; } }What is the T.C. of the following code?Is it $n^{2}$ or $n\log n$??
0 votes
0 votes
1 answer
4
Manoj Kumar Pandey asked Jun 20, 2018
307 views
We've been given an unordered list having n distinct elements,the no. Of comparison to find an element that is neither the 2nd minimum nor the 2nd maximum is?