【C】二分查找与函数1
二分查找
练习:
给定一个整型的有序数组,在数组中找到指定的一个值,如:
1,2,3,4,5,6,7,8,9,10
找出7.如果找到了,打印这个值的下标
如果没找到,就打印找不到
1. 遍历
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int k = 0;scanf("%d", &k);//输入要查找的数//遍历这个数组int i = 0;int flag = 0;//假设没找到int sz = sizeof(arr) / sizeof(arr[0]);for (i = 0;i < sz;i++) {if (arr[i] == k) {printf("找到了,下标是%d", i);flag = 1;break;}}if (flag == 0) {printf("找不到");}/*if (i == sz) {printf("找不到");}*/return 0;
}
2. 二分查找
前提:有序的数组
思路:
- 找出被查找到中间元素,使用下标来计算
- 使用中间元素与k比较,去掉一半数据
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int k = 0;scanf("%d", &k);//输入要查找的数int i = 0;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", mid);flag = 1;break;}}if (flag == 0){printf("找不到");}return 0;
}
注:
int mid = (left + right) / 2;
这种方法求中间值大部分情况下都没问题
但是当left和right非常大的时候(left+right>整形的最大值)就可能会出现问题
另一种求两个数平均值的方式:
int mid = left + (right - left) / 2;//与left right之间的大小无关
函数
函数的概念
函数 (function)(子程序)是一个完成某项特定的任务的一小段代码
C语言的程序是由无数个小的函数组合而成的,一个大的计算任务可以分解成若干个较小的函数(对应较小的任务)完成
一个函数如果能完成某项特定任务的话,复用这个函数可以提升了开发软件的效率
在C语言中一般会见到两类函数:库函数,自定义函数
库函数
标准库和头文件
C语言标准中规定了C语言的各种语法规则,C语言并不提供库函数
C语言的国际标准ANSIC规定了一些常用的函数的标准,被称为标准库
不同的编译器厂商根据ANSI提供的C语言标准就给出了一系列函数的实现,这些函数就被称为库函数
各种编译器的标准库中提供了一系列的库函数,这些库函数根据功能的划分,都在不同的头文件中进行了声明
库函数相关头文件:https://zh.cppreference.com/w/c/header
库函数的使用方法
库函数的学习和查看工具很多,比如:
C/C++官方的链接: https://zh.cppreference.com/w/c/header
cplusplus.com: https://legacy.cplusplus.com/reference/clibrary/
库函数文档的一般格式
1.函数原型
2.函数功能介绍
3.参数和返回类型说明
4.代码举例
5.代码输出
6.相关知识链接
例:
自定义函数
语法
ret_type fun_name(形式参数)
{}
函数构成:
- ret_type: 返回值类型(void表示没有返回值)
- fun_name: 函数名
- { }内:函数体
- ()内:形式参数(void表示没有参数,参数可有一个或多个)
例:完成两个整数的加和
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//函数的定义
int Add(int x, int y) {int z = x + y;return z;//返回计算的和 return x+y;
}
int main() {int a = 0;int b = 0;scanf("%d%d", &a, &b);int c = Add(a, b);//函数调用printf("%d", c);return 0;
}
VS上调试时:
F10–可以一步步的执行代码
F11–进入函数
形参与实参
以上面代码举例:
int c = Add(a, b);//a,b实际参数,简称实参
int Add(int x, int y)//x,y形式参数。简称形参
注: 当函数调用的时候,实参传递给形参到时候,形参会创建自己的空间来存放是实参的值,形参和实参不是同一块空间,对形参的修改不会影响实参,可以理解为:形参是实参的一份临时拷贝
return
return语句使用的注意事项:
- return后边可以是一个数值,也可以是一个表达式,如果是表达式则先执行表达式,再返回表达式的结果
- 函数返回类型是void时,直接写return
- return语句执行后,函数就彻底返回,后边的代码不再执行
- return返回的值和函数返回类型不一致,系统会自动将返回的值隐式转换为函数的返回类型
例:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int test() {int a = 0;scanf("%d", &a);if (a == 1)return 3.14;elsereturn -3.14;
}
int main() {int r = test();printf("%d\n", r);return 0;
}
若输入6,则输出为:
若将代码改为如下:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int test() {int a = 0;scanf("%d", &a);if (a == 1) return 5;
}
int main() {int r = test();printf("%d\n", r);return 0;
}
就会出现警告:
故要保证每种情况下都有返回值
- 如果函数中存在if等分支的语句,则要保证每种情况下都有return返回,否则会出现编译错误
- .函数的返回类型如果不写,编译器会默认函数的返回类型是int
- 函数写了返回类型,但是函数中没有使用return返回值,那么函数的返回值是未知的
设计函数返回值的时候:
1.如果函数执行的结果,需要返回给主调函数,函数就要设计返回值
2.根据需要返回的值,来设计返回的返回值
3.如果函数不需要返回追,那么写void
数组作为函数参数
例:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//实参和形参的名字可以相同
void set_arr(int arr[10],int sz) {int i = 0;for (i = 0;i < sz;i++) {arr[i] = -1;}
}
void print_arr(int arr[10], int sz) {int i = 0;for (i = 0;i < sz;i++) {printf("%d ", arr[i]);}printf("\n");
}
int main() {int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };int sz = sizeof(arr) / sizeof(arr[0]);print_arr(arr, sz);//写一个函数,将数组arr的内容全部置为-1set_arr(arr,sz);//写一个函数,打印数组的内容print_arr(arr,sz);return 0;
}
输出为:
形参的数组和实参的数组是同一个数组,数组在传参过程中不会创建一个新的数组,单独开设空间,而是传的是数组起始位置的地址,所以对形参的修改会影响实参,形参中的数组也可以不设置数组的大小
即,可以改为:
void set_arr(int arr[],int sz)
数组传参的注意事项:
- 函数的形式参数要和函数的实参个数匹配
- 函数的实参是数组,形参也是可以写成数组形式的
- 形参如果是一维数组,数组大小可以省略不写
- 形参如果是二维数组,行可以省略,但是列不能省略
- 数组传参,形参是不会创建新的数组的
- 形参操作的数组和实参的数组是同一个数组
函数的嵌套调用
嵌套调用就是函数之间的互相调用
例:
假设我们计算某年某月有多少天
可以设计2个函数:
- is_leap_year():根据年份确定是否是闰年
- get_days_of_month():调用is_leap_year确定是否是闰年后,再根据月计算这个月的天数
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int is_leap_year(int y) {if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)return 1;else return 0;}
int get_days_of_month(int y, int m) {int days[13] = { 0,31,28,31,30.31,30,31,31,30,31,30,31 };int d = days[m];//判断是否为闰年if (is_leap_year(y) && m== 2)d += 1;return d;
}
int main() {int year = 0;//年int month = 0;//月scanf("%d %d", &year, &month);//计算year年month月的天数int d = get_days_of_month(year,month);printf("%d", d);return 0;
}
函数都是对等的,函数不可以定义到另一个函数里面,但是可以嵌套调用
END…
最后:
我不去想是否能够成功,既然选择了远方,便只顾风雨兼程;
我不去想身后会不会袭来寒风冷雨,既然选择目标是地平线,留给世界的只能是背景。