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.h
left++;
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-100
int 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()
时间戳
总结
此篇主要针对折半查找算法进行例题解析，由于内容较少，添加了多道练习题。
今天就暂且更新至此吧，期待下周再会。如有错误还请不吝赐教。如果觉得对您学习有所帮助，还请留下你的支持，以防下次失踪了嗷。
作者更新不易，免费关注别手软。