【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. 二分查找

前提：有序的数组

思路：

1. 找出被查找到中间元素，使用下标来计算
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…

最后：

我不去想是否能够成功，既然选择了远方，便只顾风雨兼程；
我不去想身后会不会袭来寒风冷雨，既然选择目标是地平线，留给世界的只能是背景。