一.什么是二分查找法？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序储存结构，而且表中元素按关键字有序排列。

二.算法要求

1.必须是有序排列。

三.算法思想

例如数列   arr[]={1，2，3，4，5，6，7，8，9}          查找的数为k=3；

这里的left，right，mid记录的是数组下标

1.用left指向数列最左边的数（1），即left=0；

2.用right指向数列中最右边的数（9），即right=8；

3.用mid记录下标为（left+right）/2的数，即数组中间的数（5）；

这一步完成后，就是把arr[]数组分为了两个子数组，用arr[mid]隔开

即：      {1，2，3，4}           5         {6，7，8，9}

4.用arr[mid]与目标数k的大小进行比较，有三种情况

（1）arr[mid]=k;  即找到了

 (2)如果k比arr[mid]（即中间的那个数）大，则说明目标数（k）在右边的那个子数组中，所以就变成了在右边数组中找目标元素；方法和上面的类似，所以我们只需要将left指向改变为右边那个子数组的最左边的元素，即left=mid+1；

 (3)同理，如果k比arr[mid]小，则说明目标数（k）在左边的那个子数组中，所以就变成了在左边数组中找目标元素；我们只需要将right指向改变为左边那个子数组的最右边的元素，即right=mid-1；

5.只需要重复第四步的操作就可以把k的值的位置找到；

图解（要找的数k的值为3）

参考代码

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

输出

！！！！