Returning two array indices in an array for a given value

Question

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.

Answer 1

Yeah, bisection'll maximize the information gained from each check. If you do any sort of check other than bisection, then in the worst-case, the sought element'll be on the larger section of the selected divide.

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)$.

• T.Harish: 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.
• Nat: @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: @T.Harish Note that recursive algorithms and loops are basically two different formats for the same algorithm, so you can program this with loops or recursion; whatever's easiest for you. Most folks find recursion to be conceptually simpler. Recursion grows the stack, but for small problems like this, that shouldn't be a practical problem. Personally I'd probably do this recursively unless it was performance-critical, in which case recasting it to a loop would be a hand-optimization.
• Nat: @T.Harish BTW, this sounds like a homework problem, so I'm intentionally only pointing you in the right direction rather than writing out the actual code. You're on the right track with the idea to modify a binary search.