我对以下问题的解决方案有疑问
A magic index in an array A[l.. .n-l] 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.
我指的解决方案看起来像。假设“s”代表开始,“e”代表结束。
int fun(int a[], int s, int e)
{
if(s > e || s < 0 || e >= array.length)
return -1;
mid = (s + e)/2;
if(mid == a[mid])
return mid;
else if(mid < a[mid])
return fun(a, s, mid-1);
else
return fun(a, mid+1, e);
}
我不确定这里的结束条件。
我觉得结束条件应该就是
if(s > e)
return -1;
让我们考虑不存在魔术索引的两种极端情况
CASE 1 - going left till index 0
Say the array looks as follows a[] = {2,10,20,30,40,50}
mid = (0+6)/2 = 3 , call fun(0,2)
mid = (0+2)/2 = 1 , call fun(0,0)
mid = (0+0)/2 = 0 , call fun(0,-1)
since start > end, -1 is returned
CASE 2 - going right till the last element
Say the array looks as follows a[] = {-20,-10,-5,-4,-3,30,80}
mid = (0+6)/2 = 3 , call fun(4,6)
mid = (4+6)/2 = 5 , call fun(6,6)
mid = (6+6)/2 = 6 , call fun(7,6)
since start > end, -1 is returned
而且,我觉得解决方案中给出的额外条件永远达不到。
- 我觉得无法达到 s<0,因为我们从不从“s”中减去任何东西。我感觉's'可以取的最小值是0。也许'e'可以<0,但's'不行
- 另外我觉得 e >= array.length 是不可能的,因为我们从来没有向“e”添加任何东西。也许 's' 可以大于或等于 array.length 但不是 'e'
最佳答案
你是对的>就够了。 S 永远不会低于零,因为它要么保留要么等于 (s+e)/2+1>=s+1(因为 e>=s),所以它总是大于或等于传递的初始值,即零.同样可以证明e<=n-1总是,所以额外的条件是多余的。
关于arrays - 在数组中查找魔术索引的结束条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31619001/