0
$\begingroup$

I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array. But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 and C2 are constant values) in O(log(n)) or not

$\endgroup$
  • 1
    $\begingroup$ I'm having trouble understanding what task you want the algorithm to solve. Can you edit your question to explain your question in more detail? What is the input to the algorithm, and what do you want the output to be? I'm not sure what it means to "solve A[i]=i in a sorted array". What is the algorithm you are thinking of? Can you tell us about where you encountered this task? Can you give us any more context? It might also be helpful to tell us about what approaches you've considered and what is the fastest algorithm you have found so far. Thank you! $\endgroup$ – D.W. Aug 7 at 19:40
  • 1
    $\begingroup$ @D.W., if I understood correctly, given a sorted array, Problem 1: find $i$ such that $A[i]=i$. Problem 2: given $C_1, C_2$ find $i$ such that $A[i] =C_1 \cdot i + C_2$. $\endgroup$ – Dmitry Aug 7 at 19:57
  • $\begingroup$ Are you sure Problem 1 can be solved in $O(\log n)$ time? Can you show the algorithm in the question? $\endgroup$ – D.W. Aug 7 at 21:22
  • $\begingroup$ there is an algorithm that can solve A[i]=i in $O(\log(n))$ in a sorted array can you please provide a reference or a sketch? $\endgroup$ – greybeard Aug 9 at 1:15
2
$\begingroup$

Finding i such that A[i] = i, where A is a sorted array, needs to check every single array element in the worst case. Choose an array where A[i] = i-1 for every i except that A[k] = k for one single k. If you looked at any number of array elements other than A[k], every single one of the remaining elements could be the one you are looking for.

Now replace every array element with A[i] * C1 + C2, and unless C1 = 0, you have exactly the same problem.

Of course you can be optimistic, and often you will find i a lot quicker. Let's say you have array elements a[1] to a[1000], and you find that a[500] = 770. You now know that 1 <= i <= 499 or 770 <= i <= 1000. You just significantly reduced the number of choices. Of course my first example would have a[500] = 499, which tells you nothing apart from i ≠ 500.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what about distinct integers? $\endgroup$ – Mahdi Zakizadeh Aug 15 at 13:27

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.