C语言——二分查找

一.问题描述

编写代码在一个整形有序数组中查找具体的某个数

要求：找到了就打印数字所在的下标，找不到则输出：找不到。

二.前言

二分查找也被说为折半查找，例如当你想要从数字1-10里面找到数字9时，普遍方法是通过数组遍历查找到，不过这样的算法效率太低了，一旦数字过大就会很麻烦。所以就衍生出了折半查找，即先从中间数开始查找，舍弃另一半。不过有局限性，必须要保证是一组有序的数。

三.图文概述

我们先规定这一组数的最左端为left，最右端为right，中间为mid 。需要注意的是它们3者指向的都为下标。接下来就是对它们进行定义。

int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  int left = 0;
  int sz = sizeof(arr) / sizeof(arr[0]);
  int right = sz - 1;
    mid = (left + right) / 2;

为了right定位更加准确，这里用了sizeof来确定数组某端位置。

而关于中间值mid的计算是采用整形计算，即0+9=4.舍弃小数点后面数字。

接下来开始假想折半查找，假设我们需要寻找的是7.

第一次  可以看到我们查找时发现下标mid对应数为5是小于所找数字7的，那么说明在5前面比5还小的数字更不可能是7了，所以舍弃包括mid在内之前的数字。并重新规定left，因为前半端都没了，所以left下标变为mid+1,即为5.而right没有发生变化。

第二次  重新计算下标mid的值为7，对应数字是8，大于所找数字7，那么证明包括mid在内以后的数都是大于7的，所以可以舍弃。重新规定right下标变为mid-1.

第三次  计算下标mid的值为5，对应数字是6小于所在数字7，那么按第一次的规律舍弃包括mid之前的数，最后会发现left和right重合在了一起，对应了数字7，那么也证明了数字所在下标就是为全新的mid-6.

这就是折半查找的基本构造。

四.二分查找代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  int left = 0;
  int sz = sizeof(arr) / sizeof(arr[0]);
  int right = sz - 1;
  int k = 0;
  int mid = 0;
  int flag = 0;
  scanf("%d", &k);
  while (left<=right)
  {
    mid = (left + right) / 2;
    if (k > arr[mid])
    {
      left = mid + 1;
    }
    else if (k < arr[mid])
    {
      right = mid - 1;
    }
    else
    {
      printf("找到了，下标是%d\n", mid);
      flag = 1;
      break;
    }
  }
  if (flag != 1)
  {
    printf("找不到\n");
  }
  return 0;
}

五.细节补充

我们会发现代入的是一个while循环中，条件为left<=right.其实这里的判定为找得到这个数的前提而准备的代码条件，因为如果left>right了，那么谁都知道这只是一开始的逆重复而已，永远都找不到。

其次，每一次的arr[mid]与所在数字的对比都要对left或right进行计算矫正，如果arr[mid]过大，那么right=mid-1;反之，left=mid+1;还有一点很重要，mid的计算规则不能放到循环以外，因为mid每一次的数值都不一样，都要运用到下一次的循环中。

最后关于找不到数的情况，只要作好数字标记就行了，定一个变量flag，找得到就赋值1，找不到那么flag就不等于1，以此作为判定条件。

运行结构如图所示

六.结尾

这是我第一次发布代码题型讲解，图例也是自己画的，不好意思有点乱，希望yy们能够指正我的错误，大家一起进步~~~