在数组中查找魔术索引的结束条件

Question

我对以下问题的解决方案有疑问

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'

Answer 1

你说得对 s>e 就够了。 S 永远不会低于零，因为它要么保留要么等于 (s+e)/2+1>=s+1（因为 e>=s），所以它总是大于或等于传递的初始值，即零.类似地可以证明 e<=n-1 总是，所以额外的条件是多余的。

在数组中查找魔术索引的结束条件

ending condition in finding magic index in an array

arrays

algorithm

dynamic-programming

binary-search