【C语言】自定义函数对有序数组的二分查找，以及对二分查找会出现的问题进行补充

一、编写main函数

int main()
{
  int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
  int k = 0;
  scanf("%d", &k);
  int sz = sizeof(arr) / sizeof(arr[0]);
  int ret = binary_search(arr, k, sz); //自定义函数
  if (ret == -1)
  {
    printf("找不到\n");
  }
  else
  {
    printf("找到了，下标为：%d\n", ret);
  }
  return 0;
}

需要注意的是， 由于数组传输的是首地址，因此需要在main主调函数中提前计算出数组的大小（即sz）并传入binary_search函数。

不直接判断ret == 0而是ret == -1是因为可能要查找的值的下标就为0，因此-1更加合适。

二、binary_search函数的编写

int binary_search(int arr[], int k, int sz)
{
  int left = 0;
  int right = sz - 1;
  while (left <= right)
  {
    int mid = (left + right) / 2;
    if (arr[mid] > k)
      right = mid - 1;
    else if (arr[mid] < k)
      left = mid + 1;
    else
    {
      return mid;
    }
  }
  return -1;
}

对应的设置好left和right的范围。其中需要注意的是int mid = (left + right) / 2;必须放在循环内部，放在循环外mid就无法实时更新。

三、二分查找会出现的问题的补充说明

  int mid = (left + right) / 2;取平均值的方法，有时候是不靠谱的，因为当left和right非常大时，它们相加将会超出int能承受的最大值，就会造成溢出。当发生溢出时它们相加再相除的值便不再是它们俩的平均值。

 当然千万不能简单的觉得既然int溢出了，那用longlong就好了，那要是longlong也溢出了该怎么办，很显然这种处理方式是不对的。

而有一种方式是，假设一个柱子a高度是a，柱子b高度是b，如果希望柱子高度能一样高，可以将柱子b高出的部分分配一半给柱子a，便能够达到平分的操作。

因此在求平均值时，可以用这种方法从而避免溢出。即int mid = left + (right - left) / 2;

如果觉得作者写的不错，求给作者一个大大的点赞支持一下，你们的支持是我更新的最大动力！