[已解决]求助：请问什么是二分法？

QQ9947

天意老师讲到了二分法，但，不懂，上网查了半天也不明白什么是二分法，列举了大量的数组还是没能明白二分法的计算方法，大师们能帮我讲讲什么是二分法，二分法是怎么计算的吗？

比喻

=LOOKUP(9^9,{0,0,#VALUE!,#VALUE!,5,0.416666666666667,#VALUE!,#VALUE!,#VALUE!})

我以前对lookup函数的理解，返回的应该是5，但返回的却是0.416666666666667

能讲讲二分法在这个公式里的计算过程吗？

谢谢各位大师！！

最佳答案

月排行榜 / 总排行榜

amulee

2009-12-18 08:43

二分查找法：

　　算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

　　基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

　　假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.

　　1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

　　2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

　　3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

　　如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。

跳转到最佳答案楼层

xdwy81129

占位学习，等候解释

蝶·舞

简单地说，就是一直查找区域中间的哪个值进行比对。如果要查找的值大于区域中间的那个值则再对后半个区域进行类似的查找，如果小于区域中间的那个值，则对前半部分进行类似的查找。

QQ9947

=LOOKUP(9^9,{0,0,#VALUE!,#VALUE!,5,0.416666666666667,#VALUE!,#VALUE!,#VALUE!})

3楼朋友，能把上面这个函数里的计算过程详细说一下吗，最好能多举几个有代表性的函数再讲解一下，谢谢！！

昨晚网上搜索，还是没完全弄明白。

amulee

二分查找法：

　　算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

　　基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

　　假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.

　　1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

　　2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

　　3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

　　如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。

doggie

好久不见了，阿木师傅！

我想请教一下：

3，12，24，24,36，55，68，75，88,99

他是查找的那第三位24呢，还是第四位24呢？他是怎么查找的？

QQ9947

5楼阿木大师：不好意思，我不会二分法，你上面说到的：

1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

太深奥了，我看不懂，

=LOOKUP(9^9,{0,0,#VALUE!,#VALUE!,5,0.416666666666667,#VALUE!,#VALUE!,#VALUE!})

能讲讲二分法具体到上面这个公式里的算法吗？谢谢！！（也就是讲计算过程吧，我不懂，不知道怎么说。）

[此贴子已经被作者于2009-12-18 11:19:43编辑过]

amulee

QUOTE:

以下是引用doggie在2009-12-18 9:47:00的发言：

好久不见了，阿木师傅！

我想请教一下：

3，12，24，24,36，55，68，75，88,99

他是查找的那第三位24呢，还是第四位24呢？他是怎么查找的？

一共10个数，假设编号1-10（也可以0-9）

第一次：front=1,end=10,mid=(front+end)/2=(1+10)/2(这里取整)=5。看第五个数是36，要查找的24<36。所以在前半段找。重新设定end=mid-1=4

第二次：front=1，end=5，mid=(front+end)/2=(1+4)/2(这里取整)=2。看第二个数是12，要查找的数是24>12。所以在12和36之间找。重新设定front=mid+1=3

第三次：front=3，end=4，mid=(front+end)/2=(3+4)/2(这里取整)=24。然后看第三个数24，要查找的24=24。按照一般的二分法到这里其实就结束了。但是Excel里面的Lookup还会继续做下去：如果这时候的front要比end校，那么他会看front+1的位置是不是等于24，如果等于的话就返回front+1的那个24。Lookup函数的话就会返回第四个24。

楼主也可以看看这个流程。

doggie

太感谢师傅了！

xdwy81129

QUOTE:

以下是引用amulee在2009-12-18 8:43:00的发言：

二分查找法：

　　算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

　　基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

　　假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.

　　1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

　　2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

　　3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。

　　如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。

厉害厉害厉害。

学习了