【第三轮】8.3-8.9 CareerCup 9.3

9.3 A magic index in an array A[1.. .n-1] is defined to be an index such that A[i] =i. Given a sorted array of distinct integers, write a method to find a magic index, if
one exists, in array A.
FOLLOW UP

What if the values are not distinct?

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】binary search
Follow up: binary search with recursion. Search both sides for conditions
【时间复杂度】O(logN)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/Noahsark/48f8b1837b7c5c2ac472

【解题思路】
binary search
FOLLOW UP:
search both sides with small optimization
【时间复杂度】
O(logN)
FOLLOW UP:
worst case O(N)
【空间复杂度】
O(N) to store all the magic indeices
【gist link】
https://gist.github.com/853f9f700439860848fe
【test case】
1) 0 1 2
output: 0 1 2
2) 1 2 3
output: -1
3) -10 -5 2 2 2 3 4 7 9 12 13
output:
One magic index: 7
All magic indices as distinct array: 7
All magic indices as non-distinct array: 2 7

【解题思路】
binary search
Follow Up: binary search with some modifications

【时间复杂度】
O(logn)
Follow Up: O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/ff098814e041ce48b200

【解题思路】
Binary search + recursion (for follow up we need to compare both array[mid] and array[array[mid]])

【时间复杂度】
O(lgN)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/43595293c66549cbe51b

【解题思路】Binary search
【时间复杂度】
O(logN)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bitcpf/c5335fa99b5030343135