手写C语言之分支循环语句-二分查找算法实现（08）

• • 前言
  • 计算 n 的阶乘
  • 计算 1!+2!+3!+……+10!
  • 在一个有序数组中查找具体的某个数字n（二分查找）
  • 编写代码，演示多个字符从两端移动，向中间汇聚
  • 编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码正确则提示登录成，如果三次均输入错误，则退出程序
  • 每文一语

前面我们学习判断循环，下面将我们所学的知识进行实际的应用！

1. 计算 n的阶乘。
2. 计算 1!+2!+3!+……+10!
3. 在一个有序数组中查找具体的某个数字n。（二分查找）
4. 编写代码，演示多个字符从两端移动，向中间汇聚。
5. 编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码正确则提示登录成，如果三次均输入错误，则退出程序

#include 
int main() {

	int i = 0;
	int tep = 1;
	for (int i = 1; i <= 10; i++) {
		tep *= i;
	}
	printf("%d", tep);
	return 0;
}

这里是求得10的阶乘！那么要计算n的阶乘，那么只需要将10换成n即可！

首先需要弄懂这个算法逻辑是什么？到底应该如何去设计，前面一道题说了，计算阶乘，那么这里只是一个将阶乘求和一下就OK了。

#include 
int main() {
	int n = 0;
	scanf("%d", &n);
	int result = 0;
	for (int i = 1; i <= n; i++) {
		int temp = 1;
		for (int j = 1; j <= i; j++) {
			temp *= j;
		}
		result += temp;
	}
	printf("%d", result);
	return 0;
}

有人觉得上面的时间复杂度很高，那么如何改进呢？因为代码中用到了两处循环，如果循环次数单个是n的话，那么一共就是n的平方！所以如果我们能够把多重循环降低的话，那么可以很快的节省我们的额时间！

#include 
int main() {
	int ret = 1;
	int reslut = 0;
	for (int n = 1; n <= 10; n++) {
		ret *= n;
		reslut += ret;
	}
	printf("%d", reslut);
	return 0;
}

这里只用到了一次循环，时间复杂度就已经降低了，我们可以测试一下二者的时间！

#include 
#include 
int main() {
	int ret = 1;
	int resluts = 0;
	clock_t start_time, end_time;
	int result = 0;
	start_time = clock();
	for (int i = 1; i <= 10000; i++) {
		int temp = 1;
		for (int j = 1; j <= i; j++) {
			temp *= j;
		}
		result += temp;
	}
	end_time = clock();
	printf("%d", result);
	printf("传统的双重嵌套循环用时： %lfsn", (double)(end_time - start_time) / CLOCKS_PER_SEC);

	clock_t start_time1, end_time1;
	start_time1 = clock();
	for (int n = 1; n <= 10000; n++) {
		ret *= n;
		resluts += ret;
	}
	end_time1 = clock();
	printf("%d", resluts);
	printf("修改后的程序用时 : %lfsn", (double)(end_time1 - start_time1) / CLOCKS_PER_SEC);
	return 0;
}

我们可以发现时间对比，第二个明显比第一个要快很多！

什么叫有序数组，就是已经排好序了

传统的解决方法就是从前往后遍历，但是这样的效果太低了，速度很慢，如果成千上万的数组，那么我们查找起来就非常的麻烦！有没有什么办法呢？这里我们就需要介绍一个关于数据结构的二分查找，又叫折半法。

二分查找升级版（自定义起始值和结束值序列，并且输入查找数即可查找！）
这里运用到数组的语法，注意我们在产生有从长度的数组的时候，需要指定长度，不然会编译报错！

#include 
int main() {

	int num1 = 0;
	int num2 = 0;
	int k = 0;
	printf("请输入需要产生的有序序列数组的起始值：");
	scanf("%d",&num1);
	printf("请输入需要产生的有序序列数组的结束值：");
	scanf("%d", &num2);
	int arr[100] = { 0 };
	printf("请输入你要查找的数：");
	scanf("%d",&k);
	//产生0-num2个数值
	for (int i = 0; i < num2-num1+1; i++) {
		arr[i] = num1+i;
	}

	for (int j = 0; j < num2 - num1; j++)
		printf("%d", arr[j]);
	printf("n");
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz;

	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("找到了！下标为：%dn", mid);
			break;
		}
	}
	if (left > right) {
		printf("找不到！停止程序！n");
	}
	return 0;
}

核心算法代码

int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz;

	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("找到了！下标为：%dn", mid);
			break;
		}
	}
	if (left > right) {
		printf("找不到！停止程序！n");
	}

二分查找函数

int bin_search(int arr[], int left, int right, int key)
{
int mid = 0;
while(left<=right)
{
mid = (left+right)>>1;
if(arr[mid]>key)
{
right = mid-1;
}
else if(arr[mid] < key)
{
left = mid+1;
}
else
return mid;//找到了，返回下标
}
return -1;//找不到
}

#include 
int main()
{
	char arr1[] = "welcome to bit...";
	char arr2[] = "#################";
	int left = 0;
	int right = strlen(arr1) - 1;
	printf("%sn", arr2);
	//while循环实现
	while (left <= right)
	{
		Sleep(1000);
		arr2[left] = arr1[left];
		arr2[right] = arr1[right];
		left++;
		right--;
		printf("%sn", arr2);
	}
	//for循环实现
	for (left = 0, right = strlen(src) - 1;
		left <= right;
		left++, right--)
	{
		Sleep(1000);
		arr2[left] = arr1[left];
		arr2[right] = arr1[right];
		printf("%sn", target);
	}
	return 0;
}

#include 
int main()
{
	char psw[10] = "";
	int i = 0;
	int j = 0;
	for (i = 0; i < 3; ++i)
	{
		printf("密码错误，请重新输入:");
		scanf("%s", psw);
		if (strcmp(psw, "123") == 0)
			break;
	}
	if (i == 3)
		printf("密码三次错误！已锁定！请明日再试！n");
	else
		printf("登陆成功！n");
}

这里用到了字符串的比较函数，strcmp（）。基本形式为strcmp(str1,str2)，若str1=str2，则返回零；若str1str2，则返回正数。这个函数是用于比较字符串中字符值的大小的、从第一个字符开始比较！

加油！