前言

二分法在C语言初阶中是一种非常经典的算法，今天就来带大家认识一下它。

一.经典法

利用循环与判断语句通过遍历的方式实现

• 代码如下：

int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//升序
  int k = 7;
  int i = 0;
  for (i = 0; i < 10; i++)
  {
    if (arr[i] == k)
    {
      printf("找到了，下标是:%d\n", i);
      break;
    }
  }
  if (i == 10)
  {
    printf("找不到\n");
  }
  return 0;
}

这样雀氏能达到我们的目的，但是转念想想，是不是有点太大材小用了？

如果这个数组并不是一个有序数组，我们依然能用这种方法达到我们的目的

但是于此同时，由于我们每个数都要判断一遍，这大大增加了我们的时间复杂度。

有没有更加简单且时间复杂度更低的算法呢？

当然有，下面我们来介绍一下通过二分法实现在有序数组中的查找。

二.分法查找

1.什么是二分法？

首先对于一个有序数组，它一定是满足升序或者降序的(即前一个数的值一定比后一个数小(大))。

而我们的二分法查找，它只适用于在有序数组里查找某个数

画图解释一下

了解了二分法的基本原理，我们来具体实现一下

2.二分法的使用

还是通过代码来讲解一下

int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//升序
  int k = 7;
  int i = 0;
  int sz = sizeof(arr) / sizeof(arr[0]);//利用数组的总大小除以数组中一个元素的大小，得到数组中一共存放了几个元素
  //1
  int left = 0;
  int right = sz-1;//数组下标是数组元素个数-1
  int flag = 0;//flag的作用是标志是否找到了
  //2
  while (left<=right)//当左右都指向同一个数时还没找到，说明此数不存在
  {
    int mid = (left + right) / 2;
    if (arr[mid] == k)
    {
      printf("找到了,下标是:%d\n", mid);
      flag = 1;//令flag等于1
      break;
    }
    else if (arr[mid] < k)//mid就比k小，舍去比mid更小的数
    {
      left = mid + 1;
    }
    else//mid比k大，舍去比mid大的数
    {
      right = mid - 1;
    }
  }
  //1 2
  if (flag == 0)//判断是否找到k，如果找到，flag应等于1
    printf("没找到\n");
  return 0;
}

运行结果如下

为了防止某些初学者还是没弄懂，我们这里也画个图说明一下。

注意：由于left right mid均是整型，当出现小数是会自动把小数给舍去

假设此时的k=7

在上面的代码的注释中，我解释了中间值mid的由来。这里不再缀叙。

-此时锁定的k的范围为

第二次比较后，mid反而比k大了，那么就要舍去比mid还大的数。此时k的范围：

此时mid与left指向了同一位置，但是mid此时仍然小于k，Left=mid+1，当出现这种情况时，Left，Right，mid均指向数组下标为6的元素，如果此时还找不到k，说明这个数组中就没有看，但在图中这种情况，此时mid值与k相等，我们找到了我们想要的k，下标是mid。

3.二分法的优点与缺陷

通过上面两种方法的对比我们可以很明显的看出来，二分法的时间复杂度要远远小于经典法，比如咱们要从一个四位数中找某个数，经典法可能要运行个几千次才能找到，而对于二分法来说，可能十次不到就解决了

但是万事都是有利必有弊的，对于二分法来说，它的使用条件仅限于在一系列有序数中查找某个数，一旦在这个数组是无序的，那么二分法就无法满足我们查找的要求，而经典法通过遍历就能实现我们的要求。

总结

二分法虽好但有严苛的使用条件，在我们实际应用的过程中，一定要结合实际要求来选择是使用二分法还是经典法，万万不可不分情况随意使用。

好了，以上就是今天的主要内容了，如果你有什么疑问欢迎在评论区提出或者私信我哦，博主看到会第一时间回复滴！

如果觉得今天的内容对你有用的话，不妨点个三连再走啊，感谢大家的支持，你们的支持就是我更新的动力！！！