C语言初阶--折半查找算法

目录

练习1：在一个有序数组中查找具体的某个数字n

练习2：编写代码，演示多个字符从两端移动，向中间汇聚

 练习3：简单编写代码实现，模拟用户登录情景，并且只能登录三次

练习4：猜数字游戏实现

总结

---

练习1：在一个有序数组中查找具体的某个数字n

//在一个有序数组中查找具体的某个数字n
#include <stdio.h>
int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int k = 7;int i = 0;int sz = sizeof(arr) / sizeof(arr[0]);for (i = 0; i < sz; i++){if (arr[i] == k){printf("找到了，下标是：%d\n", i);break;}}if (i == sz){printf("找不到\n");}return 0;
}
//找到了，下标是：6

使用折半或二分查找算法（不考虑溢出）：在一个有序数组中查找具体的某个数字n

//使用折半或二分查找算法（不考虑溢出）
//在一个有序数组中查找具体的某个数字n#include <stdio.h>
int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int k = 7;int i = 0;int sz = sizeof(arr) / sizeof(arr[0]);int left = 0; //最左边元素下标int right = sz - 1; //最右边元素下标while (left <= right){int mid = (left+right) / 2; //中间元素下标，此处不考虑溢出//若考虑溢出，则使用下面一行代码保证不越界//int mid = left + (right-left) / 2;if (arr[mid] < k){left = mid + 1;}else if (arr[mid] > k){right = mid - 1;}else{printf("找到了，下标是：%d\n", mid);break;}}if (left > right){printf("找不到\n");}return 0;
}

//若考虑溢出，则使用下面一行代码保证不越界
int mid = left + (right-left) / 2;

 二分法可以改为函数的方法。直接进行调用，如下：

练习：写一个函数，实现一个整型有序数组的二分查找

练习2：编写代码，演示多个字符从两端移动，向中间汇聚

//编写代码，演示多个字符从两端移动，向中间汇聚
//welcome to china!!!!
//####################
//w##################!
//we################!!
//wel##############!!!
//···
//welcome to china!!!!//理解下面两种求数组元素个数的思路
char buf[] ="abc"; 
//[a b c \0]
// 0 1 2 3
int right = strlen(buf) - 1; //strlen(buf)求的字符串长度为3，它计算的是\0前面的元素个数
int right = sizeof(buf) / sizeof(buf[0]) - 2; //sizeof(buf) / sizeof(buf[0])求的数组元素为4   

#include <stdio.h>
#include <windows.h>
#include <stdlib.h>int main()
{char arr1[] = "welcome to china!!!!";char arr2[] = "####################";int left = 0;int right = strlen(arr2) - 1; //前面已经解释，或int right = sizeof(arr1) / sizeof(arr1[0]) - 2;while (left <= right){arr2[left] = arr1[left];arr2[right] = arr1[right];printf("%s\n", arr2);Sleep(1000); //为了更好的观察打印流程，使用windows下面的Sleep函数睡眠1000毫秒，需引入头文件windows.h。1000毫秒=1秒//windows下面的cmd窗口使用cls命令，清空屏幕，每次观察一行打印流程system("cls"); //system是一个库函数，执行系统命令cls，需引入头文件stdlib.hleft++;right--;}//前面每次打印后都清理了屏幕，最后的打印结果也被清空，可再次执行打印printf("%s\n", arr2);return 0;
}

我运行清屏cls会导致程序运行的结果不是我想要的，编译器也未报错，百度查了暂时未找到问题。只找到大概的问题是因为清屏这段代码，这里我暂且先注释掉吧，要是有大佬可以指出错误点在哪。

 私下问了许多大佬，原因：我自己的编译器不支持

#include <stdio.h>
#include <windows.h>int main()
{char arr1[] = "welcome to china!!!!";char arr2[] = "####################";int left = 0;int right = strlen(arr2) - 1; //前面已经解释，或int right = sizeof(arr1) / sizeof(arr1[0]) - 2;while (left <= right){arr2[left] = arr1[left];arr2[right] = arr1[right];printf("%s\n", arr2);Sleep(1000); //为了更好的观察打印流程，使用windows下面的Sleep函数睡眠1000毫秒，需引入头文件windows.h。1000毫秒=1秒left++;right--;}return 0;
}

 练习3：简单编写代码实现，模拟用户登录情景，并且只能登录三次

（只允许输入三次密码，如果密码正确，则提示登录成功；如果三次均输入错误，则退出程序）

//简单编写代码实现，模拟用户登录情景，并且只能登录三次。（只允许输入三次密码，如果密码正确，则提示登录成功；如果三次均输入错误，则退出程序）#include <stdio.h>
#include <string.h>
int main()
{int i = 0;char password[20] = { 0 };for (i = 0; i < 3; i++){printf("请输入密码:>");scanf("%s", password);//比较2个字符串是否相等，不能使用==，而应该使用库函数strcmp。如果函数返回值为0，表示2个字符串相等if (strcmp(password, "abcdef") == 0)  //需要引入string.h头文件{printf("登陆成功\n");break;}else{printf("密码错误\n");}}if (3 == i){printf("三次密码均输入错误，退出程序\n");}return 0;
}

基本形式strcmp(str1,str2)，string compare(字符串比较)。若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。

练习4：猜数字游戏实现

//1、电脑产生一个随机数（1-100）
//2、猜数字
//反馈猜大了、猜小了、猜对了
//建议：边写边测试，看是否能实现#include <stdio.h>
#include <stdlib.h>
#include <time.h>void menu()
{printf("**************\n");printf("****1.play****\n");printf("****0.exit****\n");printf("**************\n");  
}
void game()
{//1.生成随机数1-100//rand()%100 + 1；%100范围0-99--->+1范围1-100int ret = rand()%100 + 1; //rand()生成随机数的函数，取值范围0-RAND_MAX(32767)//printf("%d\n", ret); //用于测试//2.猜数字int guess = 0;while (1){printf("请猜数字:>");scanf("%d", &guess);if (guess < ret){printf("猜小了\n");}else if (guess > ret){printf("猜大了\n");}else{printf("恭喜你，猜对了\n");break;}}
}
int main()
{int input = 0;//空指针int *p = NULL;srand((unsigned int) time(NULL)); //时间戳。NULL定义空指针。()强制类型转换do{menu();printf("请选择:>");scanf("%d", &input);switch (input){case 1:game(); //猜数字的整个逻辑break;case 0:printf("退出游戏\n");break;default:printf("选择错误，重新选择!\n");break;}} while (input);return 0;
}

其中函数不明白的可以根据前篇的学习方法进行查阅资料进行学习。

C语言初阶--函数 中的 2.1 库函数

这里简单圈一下：

rand()

 

srand()

时间戳

 

总结

此篇主要针对折半查找算法进行例题解析，由于内容较少，添加了多道练习题。

今天就暂且更新至此吧，期待下周再会。如有错误还请不吝赐教。如果觉得对您学习有所帮助，还请留下你的支持，以防下次失踪了嗷。

作者更新不易，免费关注别手软。