Book: Cracking the Coding Interview
Question: 9.3 (page 109)
A magic index in array A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted array, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if values are not distinct?
Solution: Complexity - O(log(n))
I need to to thank you for this good read!! I definitely enjoyed every little bit of it.
ReplyDeleteI have you saved as a favorite to check out new things you post…
Here is my homepage :: łatwe chwilówki przez internet
Why you move to right when arr[mid] < mid ?? How do you know that magic index is on RHS and not LHS.
ReplyDeleteBecause the array is always sorted.
DeleteThis solution will find maximum 1 item in that array that matches. What if there are multiple ones, and question is to ask you to find all of them ?
ReplyDeleteYes, this code does not answer the follow-up part. It only finds the first magic index. It is easy though: instead of returning mid at the end, you would just put in an array or something.
Delete