C语言-折半查找（二分查找）算法详解

题目：用折半查找在一个有序数组中查找一个具体的数字n

为了方便讲解，我们假设这里的有序数组是arr[ ] = {1,2,3,4,5,6,7,8,9,10}，要查找的数是 7 。

第一步，我们标出这个有序数组的下标，并找出最左边、最右边和中间的下标：

由图可见，下标left = 0，mid = 4，right = 9。

第二步，将下标为 mid 的数字与要查找的数字 7 进行比较：

  此时因为 arr[mid] = 5 < 7,所以令 left = mid +1 = 5,right = 9不变，此时 mid = (5 + 9)/2 =7。这就缩小了一半的查找范围。

第三步，继续将要下标为 mid 的数与要查找的数字 7 进行比较：

 此时因为 arr[mid] = 8 > 7,所以令 left = 5不变，right = mid - 1 = 6，此时mid = (5 + 6 )/2 = 5。再次缩小一半的查找范围。

第四步，继续将要下标为 mid 的数与要查找的数字 7 进行比较：

  此时因为 arr[mid] = 6 < 7,所以令 left = right + 1 = 6，right = 6 不变，此时mid = (6 + 6)/2 = 6,

mid = left = right，下次再查找就可以找到了。

 这就是折半查找法的具体查找步骤，其中比较元素大小的部分，分为arr[mid] < 7,arr[mid] > 7，和arr[mid] = 7这三种情况，我们可以用 if else 分支语句实现，多次查找用 while 循环语句实现，将它们嵌套在一起就可以实现在一个有序数组中查找一个具体的数。

下面附上代码：

#include<stdio.h>
int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  //假设数组是{1,2,3,4,5,6,7,8,9,10}
  int n = 7;//要查找的数
  int m = sizeof(arr) / sizeof(arr[0]);//计算数组长度
  int right = m - 1;//右边下标
  int left = 0;//左边下标
  while (left <= right)
  {
    int mid = (left + right) / 2;//中间元素的下标
    if (arr[mid] < n)
    {
      left = mid + 1;
    }
    else if (arr[mid] > n)
    {
      right = mid - 1;
    }
    else
    {
      printf("找到了，下标是%d\n", mid);
      break;
    }
    if (left > right)
    {
      printf("找不到了\n");
    }
  }
  return 0;
}

 代码中int m = sizeof(arr) / sizeof(arr[0]);用来计算数组长度，sizeof(arr)是整个数组的大小，sizeof(arr[0])是下标为0的数组元素的大小，用整个数组大小除以下标为0的数组元素的大小即可计算出数组长度。