# Returning two array indices in an array for a given value

Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A[F] is the first value equal to x and A[L] is the last value equal to x. Your algorithm should run as fast as possible in the worst case. State the worst case running time of your algorithm.

A O(n) algorithm is very easy for this. A for loop running on the input array could easily find F,L. I think for sure there is a better algorithm. I am thinking of modifying binary search to search for the same value repetitively. I think O(logn) might not be possible, but something like $O(log ^2 n)$ might be. I am unable to come up with a precise algorithm that achieves something like this running time.

The worst-case scenarios will occur whenever bisection has to happen $O\left(\log{n}\right)$ times to find the first/last indices of the selected value, x. For example, if the array's all the same value, e.g. A=[0,...,0], then bisection'll have to occur until the algorithm whittles it down to the first 0 at $i=0$, then a separate bisective search would have to go just as many times to find the last 0 at $i=n_{\mathrm{length}}-1$.
Both searches'll be $O\left(\log{n}\right)$. But since two sequential $O\left(\log{n}\right)$ processes are still just $O\left(\log{n}\right)$, the overall algorithm's $O\left(\log{n}\right)$.
• I don't think your overall analysis is correct. You say the binary search in the worst case might happen $O\left(\log{n}\right)$ times. Each search takes $O\left(\log{n}\right)$ time. Also you don't specify many details how your algorithm works. I assume like how I did, you do binary search till you don't find that element. I was thinking of a recursion algorithm which I am yet to do precisely though. – T.Harish Dec 25 '17 at 19:13
• @T.Harish Sure, you could describe it as a recursive algorithm. Just do a recursive bisective search for the specified input value, x. Then once you find an index i at which A[i]==x, then you just need to find the first-and-last indices for the range over which A[i]==x. So, just continue the bisective search (rather than restart it) since you already know the the current slice of A is bound by a value that's less-than-x on the left and greater-than-x- on the right. – Nat Dec 26 '17 at 20:24