Find Index In Sorted Array Such That A[i] = C1 * i + C2
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 &lt;= i &lt;= 499 or 770 &lt;= i &lt;= 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.