[one_demo_11]二分查找法
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*
函数作用,冒泡排序
参数,source,数组地址;len,数组长度;orderby,排序方式,1小到大,否则反之
返回值,参数正确返回1,否则返回0
*/
int sort(int source[], int len, int orderby)
{
if (source == NULL || len == 0)
{
return 0;
}
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - 1 - i; j++)
{
if (orderby == 1)
{
if (source[j] > source[j + 1])
{
int temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
}
}
else
{
if (source[j] < source[j + 1])
{
int temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
}
}
}
}
}
/*
函数功能,从排序的整数数组中,二分查找某个整数
参数,source,要查找的对象数组;len,数组的长度;dest,要找的数
返回值,void
*/
void searcher(int source[], int len, int dest)
{
//判断参数的合法性
if (source == NULL || len == 0)
{
printf("参数不合法\n");
return;
}
//循环二分,结束条件为下限大于上限
int down = 0;//下限的下标
int up = len - 1;//上限的下标
int mid = 0;
while (down <= up)
{
//获取上限和下限的中值
mid = (down + up) / 2;
if (source[mid] == dest)
{
//数组中值等于目标,找到,返回数组中值
printf("要找的数的下标为%d\n", mid);
return;
}
else if (source[mid] > dest)
{
//如果数组中值大于目标,则改上限为中值
up = mid - 1;
}
else
{
//如果数组中值小于目标,则改下限为中值
down = mid + 1;
}
}
//如果循环结束仍没有找到,则说明不在这个数组中,返回0
printf("不存在要找的数\n");
}
//递归实现二分查找,实际上,在算法比较简单的情况下,递归的劣势,即效率低,更明显
//考虑到递归的效率问题,在递归函数内部不作参数的合法性判断
/*
函数功能,递归二分查找一个整数数组中是否存在某个整数
参数,source,int[]型,要查找的数组;down,int型,下限下标;up,int型,上限下标;dest,int型,要找的数
返回值,用以标识是否找到要找的数,返回1找到,否则,没有。
*/
int searcherd(int source[], int down, int up, int dest)
{
if (down > up)
{
printf("没有找到要找的数\n");
return;
}
int mid = (down + up) / 2;
if (source[mid] == dest)
{
printf("要找的数在数组的下标为%d\n", mid);
return 1;
}
else if (source[mid] > dest)
{
up = mid - 1;
searcherd(source, down, up, dest);
}
else
{
down = mid + 1;
searcherd(source, down, up, dest);
}
}
void main()
{
//使用随机数创建数组
time_t ts;
srand((unsigned int)time(&ts));//随机数种子
int source[100] = { 0 };
for (int i = 0; i < 100; i++)
{
source[i] = rand() % 100;
printf("%-5d", source[i]);
if (i % 10 == 9)
{
printf("\n");
}
}
int sortres = sort(source, 100, 1);
if (sortres == 0)
{
printf("参数错误,无法排序\n");
}
else
{
printf("排序后\n");
for (int i = 0; i < 100; i++)
{
printf("%-5d", source[i]);
if (i % 10 == 9)
{
printf("\n");
}
}
}
//调用二分查找函数,查找输入的数
printf("请输入要查找的数\n");
int dest = 0;
scanf("%d", &dest);
searcher(source, 100, dest);
printf("使用二分递归查找\n");
int dest2 = 0;
scanf("%d", &dest2);
int res = searcherd(source, 0, 100, dest2);
system("pause");
}