二分查找——“C”

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

各位CSDN的uu们你们好呀欢迎来到小雅兰的课堂今天我们的内容是复习之前的内容并把之前的内容的一些习题一起来做一做现在就让我们进入二分查找的世界吧

首先我们介绍的题目就是二分查找也叫折半查找

我们定义了一个整型数组为1 2 3 4 5 6 7 8 9 10这个数组所有元素的下标为0 1 2 3 4 5 6 7 8 9然后定义下标为0的元素为left定义下标为9的元素为right中间元素为mid

我们先假设要查找的元素就是7那么就可以写出这样一个式子mid=(left+right)/2;然后再进行二分查找由下图可知用二分查找的方式找到7这个元素最多只需要查找4次这样的效率远比遍历的方法的效率要高

下面我们来用代码来实现一下此功能吧

#include<stdio.h>
int main()
{
   int arr[]={1,2,3,4,5,6,7,8,9,10};
            //0,1,2,3,4,5,6,7,8,9
   int k=7;//k是要查找的数字
   int sz=sizeof(arr)/sizeof(arr[0]);
   //折半查找二分查找前提是数组有序
   int left=0;
   int right=sz-1;
   int flag=0;//一个标记变量
   while(left<=right)
   {
      int mid=(left+right)/2;
      if(arr[mid]<k)
      {
         left=mid+1;
      }
      else if(arr[mid]>k)
      {
         right=mid-1;
      }
      else
      {
         printf("找到了下标是%d\n",mid);
         flag=1;
         break;
      }
   }
   if(flag==0)
   {
      printf("找不到\n");
   }
   return 0;
}

然后我们来运行一些此代码

写到这里我们不禁会想起一个问题如果这个数组非常非常大怎么办

如果这个数组非常非常大left和right非常大left没有超出整型范围的最大值right也没有超过整型范围的最大值但left+right的和超出了整形范围的最大值就会造成溢出现象溢出之后的数据再除以2就不是平均值了所以mid=(left+right)/2这样的写法还是存在潜在风险

我们可以这样写mid=left+(right-left)/2;

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
                //0,1,2,3,4,5,6,7,8,9
    int k = 7;//k是要查找的数字
    scanf("%d", &k);
    int sz = sizeof(arr) / sizeof(arr[0]);
    //折半查找二分查找前提是数组有序
    int left = 0;
    int right = sz - 1;
    int flag = 0;//一个标记变量
    while (left <= right)
    {
        int mid = left+(right-left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else
        {
            printf("找到了下标是%d\n", mid);
            flag = 1;
            break;
        }
    }
    if (flag == 0)
    {
        printf("找不到\n");
    }
    return 0;
}

最后的结果也是非常正确的

我们再来研究研究前段时间我们学习了“函数”这一知识点那我们也是可以封装一个函数来实现此代码的那好吧一起来实操一下

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

好啦用封装函数的方法也实现啦

那么可能又会有人突发奇想说“可不可以把sz放在函数内部来求呢”这个答案当然是否定的

它的代码是这个样子

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

你运行起来会发现无论输入2之后的任意数字输出的结果都是找不到