[CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园

[CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园

[CareerCup] 9.3 Magic Index 魔法序号

 

9.3 A magic index in an array A[0.. .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?

 

这道题定义了一个魔法序号，就是一个数组的序号等于该位置的值的时候，这个序号就是魔法序号，给了我们一个有序数组，让我们来找魔法序号。这里brute force的方法就不提了，因为没啥考察的目的，对于高效的查找方法我们就要首先考虑二分搜索法，首先我们来看这种方法，没啥特别的地方，套用一般的二分查找法的格式即可，参见代码如下：

Read full article from [CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园