c语言二分法

二分法学习二分法的定义每次将目标值和查找区间的中间值进行比较根据结果将查找范围缩小一半直到找到目标元素理解有一个1到100之间的数比如66我现在可以直接猜中间值50对方回答猜小了范围就变成51到100再猜中间数75猜大了范围就变成了51到74以此类推其实c语言自带了bsearch函数去二分查找但是运用起来参数很多很麻烦时间复杂度衡量一个算法随数据n增大运行时间如何增长引用​ 如理解中的例子数据量是n每次折半需要猜的次数为log₂n次所以二分查找的时间复杂度为O( log n ), 这里默认是2为底代码实列#includestdio.hintmain(){intarr[100];intn;//要输入多少个数字inttarget;//目标数字scanf(%d,n);printf(请按从小到大的顺序输入 %d 个数字用空格隔开: \n,n);for(inti0;in;i){scanf(%d,arr[i]);}scanf(%d,target);//二分法开始intleft0;intrightn-1;intmid;intfound0;while(leftright){midleft(right-left)/2;if(arr[mid]target){printf(找到了,数字 %d 在数组的第 %d 个位置数组下标为 %d。\n,target,mid1,mid);found1;break;}elseif(arr[mid]target){leftmid1;}else{rightmid-1;}}if(found0){printf(没找到数字 %d。\n,target);}return0;}要点注意while (left right)为 不是 , 如果只有一个数或者最后只剩一个数字的时候写成 就无法得出正确结论left 和 right 取得值并不为左右边界数值是左右边界的数组序号为了之后计算出的 mid 放进数组left 和 right 改变时要将mid加减1因为mid已经猜过了写成mid left (right - left) / 2;而不是mid (right left) / 2;可以在right和left都很大的时候让他们的和不至于过大溢出超出了int的最大值注意向下取整了中间值有两个时自动取了小的输入的数组必须为从小到大的数 如果想输入无序的数组 可以在二分法之前加一个冒泡函数之类的让其排序for(inti0;in-1;i){for(intj0;jn-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}加深理解没有注意要点 3( right left 等于 mid 时) 不能向右取整​ 假设区间为闭区间【5758】要找的数字为57letf 0right 1向上取整 mid1, 即58​ arr[mid] target, 于是 right mid 区间仍然为【01】陷入死循环。-------易错点如果找不到时停在哪里了​ 数字不存在循环结束之后此时 left right , 且 left right 1 此时left停下的地方恰好是这​ 个数字应该插入的位置​ 例如​ 比如数组是 [1, 3, 5, 7]找 4​ 第一次 mid 1指向34 比 3 大mid加1等于2 left 变成 2​ 第二次 mid 2指向54 比 5 小mid减1等于1right 变成 1​ 此时 left right 循环结束 此时left停留的位置arr[2], 就是4应该放的位置如果数字有重复元素时怎么找第一个和最后一个​ 找到目标之后不要用break退出循环定义一个常量记录现在的mid值即下标值方便找位​ 置重复循环mid值也在变化最后根据它的值描述在数列中的位置。要分向左寻找和向右寻找// 向左查找intf(intarr[],intn,inttarget){intleft0;intrightn-1;intans-1;// 用来记录找到的下标-1表示没找到while(leftright){intmidleft(right-left)/2;if(arr[mid]target){ansmid;// 1. 找到了先记录此时的下标rightmid-1;// 2. 别退出继续向左找}elseif(arr[mid]target){leftmid1;}else{rightmid-1;}}returnans;}左闭右开的写法intleft0;intrightn;// 注意这里是 n ,指向最后一个元素后面的位置取不到while(leftright){// 是 intmidleft(right-left)/2;if(arr[mid]target){returnmid;}elseif(arr[mid]target){leftmid1;}else{rightmid;// 这里是 mid不是 mid - 1}}return-1;在左闭右开范围内的是数组元素的下标 取不到右边界right的值左开右闭就是指大于等于left小于right当left和right相等时自然不成立了所以条件是left right因为取不到right的值所以直接让它等于mid因为mid已经取过了也不要mid的值​​