2
$\begingroup$

I was wondering what is the most efficient way to find the a number in an array with the following conditions:

Array $A$ of size $n$ divided into even parts in the size of $k$

  • every element in each part is bigger than all the elements in the part before (Lets say in the left)
  • every element in each part is smaller then then every elements in the part after it (lets say on the right)

At this moment after trying couple of ways I am under the impression that the only way is $O(n)$

Is it correct?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You can solve this in $O(\log(n/k) + k)$. $\endgroup$ – Yuval Filmus Aug 25 '17 at 12:59
  • $\begingroup$ @YuvalFilmus I managed to solve this in $O(log(n/k)+2k)$ Because as I understand there is no way to distinguish between two parts that are one near the other - lats say i know that my number is bigger then the first number in part $A$ and smaller than the first number in part $B$ I know for sure that my number is somewhere in parts $B$ or $A$ correct? so where is my mistake? $\endgroup$ – misha312 Aug 25 '17 at 13:23
  • $\begingroup$ I'm not sure what you mean. The complexity classes $O(\log(n/k)+k)$ and $O(\log(n/k)+2k)$ are identical. $\endgroup$ – Yuval Filmus Aug 25 '17 at 13:25
  • 1
    $\begingroup$ I would call that $O(\log (n) + k)$ because $O(\log(n/k)+k) = O(log(n)-\log(k)+k)$ and $O(k-\log(k)) = O(k)$ $\endgroup$ – ratchet freak Aug 25 '17 at 13:53
0
$\begingroup$

Choose an arbitrary representative from each part. Using binary search, you can find the two representatives which bracket the given element. You can then look for your given element in the $2k$ elements comprising the two parts that the representatives belong to. This algorithm takes time $O(\log(n/k) + k) = O(\log n + k)$, interpolating between the cases $k=1$ (sorted array, $O(\log n)$) and $k = n$ (unsorted array, $O(n)$).

Improve this answer
$\endgroup$
  • $\begingroup$ Great that's exactly what I did, binary search + loop. But one more thing I am sorry for the ignorance but what is interpolation? (I am already tried to translate it) $\endgroup$ – misha312 Aug 25 '17 at 14:37
  • $\begingroup$ Sorry, I meant "interpolating". I meant it in a sense similar to linear interpolation. $\endgroup$ – Yuval Filmus Aug 25 '17 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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