当前位置：首页 > article >正文

用c语言实现二分法

article 2025/6/29 10:45:26

#首先二分法的优点是可以在有序的和大量的数组更快的查找到目标；

（简单介绍一下二分法）

二分法，也称为二分查找，是一种在有序数组中查找特定元素的算法。它的基本思想是通过将数组分成两部分，然后确定目标元素可能存在的那一部分，然后继续在该部分中进行查找，直到找到目标元素或确定目标元素不存在为止。

具体来说，二分法的步骤如下：
1. 首先确定数组的中间元素。
2. 如果中间元素等于目标元素，则返回中间元素的索引。
3. 如果中间元素大于目标元素，则在左半部分继续查找。
4. 如果中间元素小于目标元素，则在右半部分继续查找。
5. 重复上述步骤，直到找到目标元素或确定目标元素不存在。

二分法的时间复杂度为O(log n)，因此它是一种高效的查找算法。它通常用于有序数组或有序列表中查找元素，例如在查找算法中常用的二分查找。

以下就是代码加注释；

简单介绍一下思路：

1.输出数组 2.获得数组长度，目标元素 3.进行判断（详情请见代码）

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>int bin(int arr[], int n, int key)
{int left = 0;      //左下标int right = n - 1; //右下标while (left<=right){int mid = left + (right - left) / 2;if (arr[mid] > key){//当中间值大于key，则目标在mid的左侧,于是-1，对半砍去midright = mid - 1;}else if (arr[mid]<key){//当中间值小于key，则目标在mid的右侧,于是+1，对半砍去midleft = mid + 1;}else{return mid;}}return -1;
}int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//            0 1 2 3 4 5 6 7 8 9int n = sizeof(arr) / sizeof(arr[0]);//确定数组的长度int key= 8;//此为目标元素int ok = bin(arr, n, key);//将我们要实现的功能外包出去；//最后进行判断if (ok != -1){//由外包函数查找完输出printf("这个值的下标为%d\n", ok);}else{//超出数组的长度，即不存在printf("这个值不在数组中\n");}return 0;
}

（代码）

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int bin(int arr[], int n, int key)
{
int left = 0; //左下标
int right = n - 1; //右下标

   while (left<=right)
   {
       int mid = left + (right - left) / 2;

       if (arr[mid] > key)
       {
           //当中间值大于key，则目标在mid的左侧,于是-1，对半砍去mid
           right = mid - 1;
       }
       else if (arr[mid]<key)
       {
           //当中间值小于key，则目标在mid的右侧,于是+1，对半砍去mid
           left = mid + 1;
       }
       else
       {
           return mid;
       }
   }
   return -1;
}

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 n = sizeof(arr) / sizeof(arr[0]);
   //确定数组的长度
   int key= 8;
   //此为目标元素
   int ok = bin(arr, n, key);
   //将我们要实现的功能外包出去；

   //最后进行判断
   if (ok != -1)
   {
       //由外包函数查找完输出
       printf("这个值的下标为%d\n", ok);
   }
   else
   {
       //超出数组的长度，即不存在
       printf("这个值不在数组中\n");
   }

return 0;
}

查看全文

http://www.lryc.cn/news/2420571.html