当前位置: 首页 > news >正文

[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");
}

 

相关文章:

  • [one_demo_12]递归打印*\n*.*.\n*..*..\n图形
  • c
  • network
  • 使用javadoc生成项目的帮助文档
  • [one_demo_13]ArrayList去除重复的元素
  • web项目发布到tomcat的两种方式
  • androidBasic
  • mybatis使用like模糊查询防sql注入写法
  • maven整合ssm项目中报org.apache.ibatis.binding.BindingException: Invalid bound statement (not found)
  • dubbo简介
  • FastDFS简介
  • redis集群
  • solr集群
  • ssm框架web项目配置全局异常处理
  • ActiveMQ
  • 2018一半小结一波
  • Angular 响应式表单 基础例子
  • axios请求、和返回数据拦截,统一请求报错提示_012
  • co.js - 让异步代码同步化
  • Docker 笔记(2):Dockerfile
  • ES6, React, Redux, Webpack写的一个爬 GitHub 的网页
  • Github访问慢解决办法
  • gitlab-ci配置详解(一)
  • Java Agent 学习笔记
  • Js基础知识(一) - 变量
  • learning koa2.x
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • php中curl和soap方式请求服务超时问题
  • SQL 难点解决:记录的引用
  • swift基础之_对象 实例方法 对象方法。
  • uva 10370 Above Average
  • windows下如何用phpstorm同步测试服务器
  • 大型网站性能监测、分析与优化常见问题QA
  • 技术:超级实用的电脑小技巧
  • 理解在java “”i=i++;”所发生的事情
  • 两列自适应布局方案整理
  • 聊聊spring cloud的LoadBalancerAutoConfiguration
  • 前端学习笔记之观察者模式
  • 如何使用 JavaScript 解析 URL
  • 双管齐下,VMware的容器新战略
  • 原生js练习题---第五课
  • LevelDB 入门 —— 全面了解 LevelDB 的功能特性
  • ​LeetCode解法汇总1276. 不浪费原料的汉堡制作方案
  • ​secrets --- 生成管理密码的安全随机数​
  • ​七周四次课(5月9日)iptables filter表案例、iptables nat表应用
  • #if 1...#endif
  • #Z0458. 树的中心2
  • (2)STL算法之元素计数
  • (2.2w字)前端单元测试之Jest详解篇
  • (Matlab)使用竞争神经网络实现数据聚类
  • (NSDate) 时间 (time )比较
  • (pojstep1.1.1)poj 1298(直叙式模拟)
  • (安全基本功)磁盘MBR,分区表,活动分区,引导扇区。。。详解与区别
  • (三)mysql_MYSQL(三)
  • (深度全面解析)ChatGPT的重大更新给创业者带来了哪些红利机会