二分查找C语言实现#define_CRT_SECURE_NO_WARNINGS//练习1多个字符从两端移动向中间汇聚//编写代码演⽰多个字符从两端移动向中间汇聚//#includestdio.h//#includestring.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;//}//#includestdio.h//#includestring.h//#includewindows.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;//}//#includestdio.h//#includestring.h//#includewindows.h//#includestdlib.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//#includestdio.h//#includetime.h//#includestdlib.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;//}//优化一下输入进程//#includestdio.h//#includetime.h//#includestdlib.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这里涉及到了数值溢出在博主的另一篇文章中单独介绍了数值溢出的问题以及如何避免给博主点点关注支持一下后续给大家带来更多实用的知识和技巧。