0
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – T.Harish
    Dec 25, 2017 at 19:13
  • $\begingroup$ @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. $\endgroup$
    – Nat
    Dec 26, 2017 at 20:24
  • $\begingroup$ @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. $\endgroup$
    – Nat
    Dec 26, 2017 at 20:27
  • $\begingroup$ @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. $\endgroup$
    – Nat
    Dec 26, 2017 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.