in Others retagged by
138 views
0 votes
0 votes
Let A be a sorted array of distinct integers of length n. Design an algorithm to find an index i such that A[i] = i if such an index exists. If there are more than one such indices, you may output any one. If no such index exists then the algorithm outputs −1. The asymptotic time complexity of the fastest algorithm for this problem, assuming the array is already available, is Θ ______________________________
in Others retagged by
138 views

1 comment

Binary Search would help. In worst case, running time is $\Theta(\log n)$ and in best case, it is $\Theta(1).$
0
0

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
4