[C语言]二分法查找(有序数组)
二分查找(折半查找)
每当我们需要在一个有序数组里查找到一个自己想要的数字时,通常的方法是使用循环一个个的去寻找。但是如果数组里的数量特别大时,这种方法便会显得笨重。因此我们便可以使用二分查找来寻找我们需要的数字。
注意:这种算法只能在有序数组里使用,如果是无序数组这种方法无法使用!
算法思想:
1、我们需要两个变量来充当数组的最左端下标和最右端下标
2、另外设置一个变量来充当数组的中间下标。
3、这三个变量是会改变的。
代码:(头文件和函数我就不写了)
int left = 0;
int right = 0;
int mid = 0;
int num = 0;
int array[10] = { 0 };//以上都是初始化
for ( int i = 0 ; i < 10 ; i++ )
{
array[ i ] = i + 1 ;
}//设置1到10的有序数组
scanf ( “%d”, & num);//想要找的数字
right = sizeof(array) / sizeof (array[ 0 ]);
while( 1 )
{
mid = ( left + right ) / 2 ;//数组中间下标
if ( array [ mid ] > num)
{
right = mid - 1;
//说明了这个中间下标的数字比我们想要的数字还大,并且在右边.
}
else if ( array [ mid ] < num)
{
left = mid + 1;
//说明了中间下标的数字比想要的数字小,并且在左边。
}
else
{
printf("%d\n",mid);
//输出我们所想要的数字下标
break;
//同时还要跳出循环
}
if(left > right)
{
printf(“找不到\n”);
break;
}
}
代码写到这,大体的思路便已经介绍完了
一开始不理解的话,可以画一个图来辅助自己理解
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
int left = 0, right = 0, mid = 0, num = 0, array[10] = { 0 };
scanf("%d", &num);
for (int i = 0;i < 10;i++)
{
array[i] = i + 1;
}
right = sizeof(array) / sizeof(array[0]);
while (left<=right)
{
mid = (left + right) / 2;
if (array[mid] > num)
{
right = mid -1 ;
}
else if (array[mid] < num)
{
left = mid + 1;
}
else
{
printf("该数字的下标为:%d", mid);
break;
}
}
if(left>right)
{
printf("找不到\n");
}
return 0;
}
上一篇: C语言->二分查找