c - 二分查找中的结束索引

Question

我有几个关于二分搜索的问题。

1. 在下面的代码中，我从 main 传递 fun(array, 0, len-1)。传递“len”作为结束索引也可以吗？我认为没关系，也已经验证了答案。

我觉得唯一的区别是，数组中中间元素之后的部分会少一次计算，而中间元素之前的数组部分会增加一次计算。

此外，在执行 mid = (s+e)/2 时，通常整数除法会取下限值。如果我们做 mid = (ceiling)(s+e)/2 呢？再说一次，我觉得唯一的区别是，在中间元素之后的数组部分将少一项计算，而在中间元素之前的数组部分将增加一项计算。

下面是我的代码

#include <stdio.h>    
int key = 0;
int len = 0;

int main(void)
{
 int a[] = {1,2,3,4,5,6,7,8,9};

 printf("Enter key : ");
 scanf("%d",&key);

 len = sizeof(a)/sizeof(*a) - 1;

 printf("Array : ",print(a));
 //printf("Element found at index : %d",fun(a,0,len-1));
 printf("Element found at index : %d",fun(a,0,len));

 printf("\n");
 return 0;
}

int fun(int a[], int s, int e)
{
 int mid = 0;
 mid = (s+e)/2;

 if(a[mid] == key)
  return mid;

 if(s == e)
  return -1;

 if(a[mid] > key)
  fun(a,s,mid-1);
 else
  fun(a,mid+1,e);
}
int print(int a[])
{
 int i = 0;
 for(i=0;i<len;i++)
  printf("%d ",a[i]);
 printf("\n");
}

Answer 1

是的，传递len和len-1只会改变递归调用的数量，对于mid元素之前的元素和mid元素之后的元素来说，它会有所不同元素。

使用ceil也是如此。因此，是的，根据数组中的索引，不同元素的递归调用数量可能会有所不同。

这两项更改都会给您正确的结果。