当前位置：首页 > news >正文

新手小白学习计算机的第十天（老王专场）

news 2026/8/15 8:49:52

二分查找：C语言实现

#define_CRT_SECURE_NO_WARNINGS//练习1：多个字符从两端移动，向中间汇聚//编写代码，演⽰多个字符从两端移动，向中间汇聚//#include<stdio.h>//#include<string.h>//int main()//{// char arr1[] = "welcome to China !!!!!!!!!!!!!!!";// char arr2[] = "################################";// int left = 0;// int right = 0;// right = strlen(arr2);// while (left <= right)// {// arr2[left] = arr1[left];// left++;// arr2[right] = arr1[right];// right--;// printf("%s\n", arr2);// }// return 0;//}//#include<stdio.h>//#include<string.h>//#include<windows.h>//int main()//{// char arr1[] = "welcome to China !!!!!!!!!!!!!!!";// char arr2[] = "################################";// int left = 0;// int right = 0;// right = strlen(arr2);// while (left <= right)// {// arr2[left] = arr1[left];// left++;// arr2[right] = arr1[right];// right--;// printf("%s\n", arr2);// Sleep(1000);//S;eep()windows自带，单位是毫秒// //让程序进程变慢，能够清晰地感受到程序的变化// }// return 0;//}//#include<stdio.h>//#include<string.h>//#include<windows.h>//#include<stdlib.h>//int main()//{// char arr1[] = "welcome to China !!!!!!!!!!!!!!!";// char arr2[] = "################################";// int left = 0;// int right = 0;// right = strlen(arr2);// while (left <= right)// {// arr2[left] = arr1[left];// left++;// arr2[right] = arr1[right];// right--;// printf("%s\n", &arr2);// Sleep(1000);//S;eep()windows自带，单位是毫秒// //让程序进程变慢，能够清晰地感受到程序的变化// system("cls");//system用来执行系统命令// //system("cls")；用来清理屏幕// }// printf("%s\n", &arr2);// return 0;//}//练习2：//#include<stdio.h>//#include<time.h>//#include<stdlib.h>//int main()//{// int left ,right, mid,i,input;// /*int right = 0;*/// //int mid = 0;// int arr[1000] ;// //int i = 0;// //int input = 0;// printf("请输入数组长度\n");// scanf("%d", &input);// for (i = 0; i < input; i++)// {// arr[i] = i;// }// srand((unsigned int)time(NULL));// int a = rand() % input ;// printf("%d\n", a);// left = 0;// right = input - 1;// //mid = (left + right) / 2;// while (left <= right)// {// mid = (left + right) / 2;// if (a < arr[mid])// {// right = mid - 1;// }// else if (a > arr[mid])// {// left = mid + 1;// }// else// {// printf("找到了，要找的数为：%d,下标为：%d", a, mid);// break;// }// }// return 0;//}//优化一下输入进程//#include<stdio.h>//#include<time.h>//#include<stdlib.h>//#define INPUT_MAX 1000//int main()//{// int left, right, mid, i, input;// /*int right = 0;*/// //int mid = 0;// int arr[INPUT_MAX];// //int i = 0;// //int input = 0;// printf("请输入数组长度\n");// //防止出现数值溢出// while (scanf("%d", &input) != 1 || input > INPUT_MAX)// {// printf("输入非法，请重新输入\n");// }// for (i = 0; i < input; i++)// {// arr[i] = i;// }// srand((unsigned int)time(NULL));// int a = rand() % input;// printf("%d\n", a);//该行代码可以不运行，// //这是一个可以选定范围进行二分查找的程序// //可以改进为用于演示二分查找的示例// //也可以改为猜数字游戏// left = 0;// right = input - 1;// //mid = (left + right) / 2;// while (left <= right)// {// mid = (left + right) / 2;// if (a < arr[mid])// {// right = mid - 1;// }// else if (a > arr[mid])// {// left = mid + 1;// }// else// {// printf("找到了，要找的数为：%d,下标为：%d", a, mid);// break;// }// }// return 0;//}//再次优化，可以让改代码更结构化，更有序//#include <stdio.h>//#include <stdlib.h>//#include <time.h>////// 宏定义，便于修改数组最大容量//#define MAX_ARR_SIZE 1000/////**// * brief 二分查找函数// * param arr 有序升序数组// * param left 左边界下标// * param right 右边界下标// * param key 需要查找的值// * param count 传出参数，统计查找循环次数// * return 找到返回下标；找不到返回 -1// *///int binarySearch(int arr[], int left, int right, int key, int* count)//{// *count = 0;// while (left <= right)// {// (*count)++;// // 防溢出写法，替代 (left + right) / 2// int mid = left + (right - left) / 2;//// if (key < arr[mid])// {// right = mid - 1;// }// else if (key > arr[mid])// {// left = mid + 1;// }// else// {// // 找到目标// return mid;// }// }// // 查找失败// return -1;//}////int main(void)//{// int arr[MAX_ARR_SIZE];// int len;// int target;// int findIndex;// int searchCnt;//// printf("请输入数组长度(1~%d)：", MAX_ARR_SIZE);// if (scanf("%d", &len) != 1 || len <= 0 || len > MAX_ARR_SIZE)// {// printf("输入非法！\n");// return 1;// }//// // 构建升序数组 arr[0]=0, arr[1]=1 ... arr[len-1]=len-1// for (int i = 0; i < len; i++)// {// arr[i] = i;// }//// // 初始化随机种子，程序内仅执行一次// srand((unsigned int)time(NULL));// // 随机选取数组中存在的数字 [0, len-1]// target = rand() % len;// printf("待查找数字：%d\n", target);//// // 调用二分查找// findIndex = binarySearch(arr, 0, len - 1, target, &searchCnt);//// if (findIndex != -1)// {// printf("查找成功！数字 %d 下标：%d\n", target, findIndex);// printf("一共循环查找 %d 次\n", searchCnt);// }// else// {// printf("查找失败，数组中不存在该数字\n");// }//// return 0;//}//#include <stdio.h>//// int main()// {// int arr[] = { 1,2,3,4,5,6,7,8,9,10 };// int left = 0;// int right = sizeof(arr) / sizeof(arr[0]) - 1;// int key = 7;//要找的数字// int mid = 0;//记录中间元素的下标// int find = 0;// while (left <= right)// {// mid = (left + right) / 2;//// //这样求平均值的写法存在问题，当left和right都很大时，// //二者相加，可能会超出整形范围，导致溢出。////// if (arr[mid] > key)// {// right = mid - 1;// }// else if (arr[mid] < key)// {// left = mid + 1;// }// else// {// find = 1;// break;// }// }// if (1 == find)// printf("找到了,下标是%d\n", mid);// else// printf("找不到\n");// }//////如何求平均值才能避免溢出？//mid = left / 2 + right / 2;//这样的写法貌似很合理，举个例子：left = 3,right = 7.//二者的平均值为5，但用上面的写法平均值为3/2 = 1 7/2 = 3//mid = 4 XXXXX// 防溢出写法，替代 (left + right) / 2//int mid = left + (right - left) / 2;//此代码就很好的避免了溢出的问题//如下图所示：//// //int mid = left + (right - left) / 2;// |----|// | 1 |// |----| |----|// | 1 | | 2 |// |----| -----------------|----|// | | | |// | | | |// | | | |// | | | |// | | | |//-----------------------------------------------// left right