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
$\begingroup$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ what about distinct integers? $\endgroup$ Commented Aug 15, 2020 at 13:27
A[i]=iin $O(\log(n))$ in a sorted array can you please provide a reference or a sketch? $\endgroup$