0
$\begingroup$

I need help on this question: Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that runs in time O(log n).

How I can proceed? Thanks a lot!

$\endgroup$

closed as unclear what you're asking by D.W., Luke Mathieson, David Richerby, Juho, Raphael Jun 29 '15 at 10:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Did you try anything yet? Where did you get stuck there? $\endgroup$ – Juho Jun 28 '15 at 14:53
  • $\begingroup$ I I tried using a modification of binary search. I don't think is the right way. $\endgroup$ – Ivankin Jun 28 '15 at 14:57
  • 2
    $\begingroup$ Why not? Binary search is a perfectly good way to do this. $\endgroup$ – Rick Decker Jun 28 '15 at 16:13
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 29 '15 at 10:02
1
$\begingroup$

Hint: Define $B[i] = A[i] - i$. What can you say about the array $B$? Use the fact that $A$ contains distinct integers.

$\endgroup$

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