二分查找Binary Search通过不断缩小查找区间在有序数组中高效定位目标值汉诺塔Tower of Hanoi则借助辅助杆将圆盘按规则从源杆移动到目标杆。两者都体现了分治思想二分查找每次将问题规模减半汉诺塔则将 n 个圆盘的问题拆解为 n-1 个圆盘的子问题。下面以有序数组[1, 3, 5, 7, 9]查找目标值7为例演示二分查找过程中left、right、mid指针的移动初始left0, right4, mid2arr[2]5 7目标在右半区更新leftmid13, right4, mid3arr[3]7 7命中返回下标 3逐步说明第 1 步left 0right 4mid (04)/2 2。此时arr[2] 5因为5 7说明目标值在右半区所以将left更新为mid 1 3。第 2 步left 3right 4mid (34)/2 3。此时arr[3] 7恰好等于目标值查找成功返回下标3。整个过程中查找区间从[0, 4]缩小到[3, 4]最终定位到目标值体现了二分查找每次将问题规模减半的特点。模型类似一维数组的表格上层是数据下层是下标。最左边最右边中间left right middle和数学的那个比大小有点像通过放缩不断缩小比较范围运用函数 left right middle target return -1#includestdio.hint binarysearch(int arr[],int left ,int right,int taeget);{if (leftright)return -1;int midleft(right-left)/2;if arr[mid]targetreturn mid;else if(arrr(mid)target)return binarysearcharr,left,mid1,target;elsereturn binarysearch(arr,right,mid-1,target);}注意定义函数和调用不一样定义时要把全部信息写完整但调用时只写参数定义时原位置只是放了个盒子不是说它就是那个含义只是说那里可以放两个参数left也可以是mid汉若塔问题公式2的n次方-11.一次转一个2.大的在下面3.顺序从上往下因此这就导致了多杆问题公式hanoi(n,源辅助目标)例题:#include(stdio.h)void hanor(n,char post1,post2,post3){ if(n0)return 0;hanor(n-1,post1,post3,post2);printf(“%C-%C\n”,post1,post3);hanor(n-1,post2,post1,post3);}}它一定告诉你有多少片要移动的总结二分查找和汉诺塔虽然解决的问题不同但都基于分治思想共同点两者都将大问题拆解为规模更小的子问题。二分查找每次将查找区间缩小一半汉诺塔将 n 个圆盘的问题转化为 n-1 个圆盘的移动问题。不同点用途不同二分查找用于在有序数组中查找目标值汉诺塔用于按规则移动圆盘。结果不同二分查找返回目标值的下标或 -1汉诺塔输出一系列移动步骤。递归方式不同二分查找是单路递归每次只进入一个分支汉诺塔是双路递归每次递归调用两次自身。参考资料二分查找 - 维基百科汉诺塔 - 维基百科分治算法 - 维基百科