蔡岫勍C语⾔：关于⼆分法
⼆分法:⼆分法是数学⾥⾯较为常见的算法之⼀，⼜可以被称为⼆分查，它描述了在有序集合中搜索特定值的过程。⼆分法顾名思义就是⼀分为⼆。⼴义的⼆分查是将问题的规模尽可能的缩⼩到原有的⼀半。
⼀般来说，我们都会遇到这种问题：给定⼀个由数字组成的有序数组，并给你⼀个数字，请你判断这个数字是否在数组中。 像这类问题我们⼀般会想到，⽤这个数字与数组⾥的数逐个⽐较，但是这样⼀来会很⿇烦，这个时候就会⽤到⼆分法，将数组中的数⼀分为⼆，⽤这个数同分开的中间值相⽐较，如果⼤于则将前半段数组中的数舍弃，在后半段数组中再次⼆分，这样⼀来，往复循环就可以将数组中的数都判断出来。
金冷法>冶金自动化所以⼆分法查原理：
(1).确定中间值与左右边界的值(下标）
(2).查的数与中间⽐较，如果中间值⼤于要查的数则往左边查询，反之右边）
(3).判断没有查到的情况：如果扫描到左边界的元素个数⼤于右边边界的元素个数，则表⽰没有到
注意：⼀般数组会是⽆序的，在利⽤⼆分法之前应该先进⾏升序排序或降序排序，然后进⾏⼆分法 对于⼆分查中使⽤的术语，这是⽹上查阅的有关说明
⼆分查是⼀种在每次⽐较之后将查空间⼀分为⼆的算法。每次需要查集合中的索引或元素时，都应该考虑⼆分查。如果集合是⽆序的，我们可以总是在应⽤⼆分查之前先对其进⾏排序。但要注意排序的成本
加拿大飞蓬
target: 要查的值
index: 查时的当前位置
left 和 right: 左右指针
mid: 左右指针的中点，⽤来确定我们应该向左查还是向右查的索引
在最简单的形式中，⼆分查对具有指定左索引和右索引的连续序列进⾏操作。这就是所谓的查空间。⼆分查维护查空间的左、右和中间指⽰符，并⽐较查⽬标或将查条件应⽤于集合的中间值；如果条件不满⾜或值不相等，则清除⽬标不可能存在的那⼀半，并在剩下的⼀半上继续查，直到成功为⽌。如果查以空的⼀半结束，则⽆法满⾜条件，并且⽆法到⽬标。青岛科技大学校园网
注意：
（1）⼆分法搜索可以采⽤许多替代形式
（2）可能并不总是直接搜索特定值
（3）你不⼀定能直接缩⼩⼀半的查范围
总之，使⽤⼆分法，应该注意数字下标，否则是很容易出错的第二次经济普查
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议