二分查找算法 得一些疑惑。
先来一个code sectiondefine int[] arr = {low..high},low=0,high=arr.length - 1 ,mid = 0,key= n;
while(low <= high) {
mid = (low + high) / 2; //每次去区间的中间索引。
if(arr == key) return mid; //恰好相等，则直接返回 mid
if(arr > key) high = mid - 1;//当前索引数据大于key,则知道,key必然在 arr中，这个时候low不变，high = mid - 1;
if(arr < key) low = mid + 1; //当然索引数据小与key ,则知道,key必然在arr中，这个时候high 不便。low= mid +1;
}
//找不到 -1
return -1;
用公式给出则：
mid = arr;
key < arr;
key > arr;
如果思路按照这个走下去， 发现这个算法很有意思， 至少我感觉就很爽。
例如 有这么一个序列：
1.2.3.4.5.6.7.8.9.10
我要找 7。按如上算法推理过程如下：
n{1.2.3.4.5.6.7.8.9.10};
low = 0;
high = n.size;
10/2 = 5
根据规则 这个时候 high是不变得，low = (10/2) + 1;
继续： (low = 6+ high = 10) / 2 = 8;
8已经大于7,所以low = 6 + high = 10 - 1) / 2= 7 于是找出来了。我发现这么一个问题，如果按四舍五入，那么结果应该是 8， 这样子就会陷入一种循环中去了。
实际上，写道这里，可能各位朋友还不知道我想表达什么意思。 :(
我主要是对于这样一个推力过程感到困惑，抽象思维太弱。 各位可以给出一个严谨的推理过程么？ 还有，二分查找算法主要用于什么地方？
我数学基础很差， 以前一直逃避算法 这些东西，觉得自己搞不定。 例如这个程序，我现在也大致知道他的原理和用法，但是对于其内部的一个抽象过程，我很迷糊， 这样，要不多长时间我可能就忘记了。 只有真正明白了 内在，才是真正掌握了这个算法。而且，我发现这个算法思维过程在现实世界中也能找到很多对应。我想这就是数学的美丽把？
我最近对数学 极为感兴趣。 觉得每天最爽的消磨时间就是找一个算法，然后去找他的内在机理。 这个算法也是我在研究顺序插入排序的时候 突然冒出来的想法， 这样子就可以每次减少一倍的查询时间.:)
我没有受过专业的科学训练. 所以在描述和思维上还请见谅. :) 在计算机的实现中，整数‘/’是按下取整来操作的，不是按四舍五入。 简单来说,是否四舍五入是可以人为控制的 具体如何结束在你的算法控制 各位，谢谢回复. 不过，我想了解的是这样一个推理过程的数学描述？！
就是数学规则， 一种抽象过程。
我自己稍微有个想法， 今天吃饭回来时突然想出来的，那就是不管 low .. high 得位置如何变化， 他们的和都是 这个集合的长度.
我现在还在公司，没经历去思考，今天晚上整理写思路，再求证下。
我觉得各位可能觉得这个算法实在简单？
我想要这个算法背后的一个具体的数学推理过程，也就是抽象过程。
:) 不对呀，如果在10000个元素的表中查找噢乖一个元素，该元素位于第2个。
经过多次折半，最终low 可能会是1，high可能是3. 1+3怎么等过等于集合长度了。 原帖由 liangbch 于 2008-12-15 16:53 发表 http://bbs.emath.ac.cn/images/common/back.gif
不对呀，如果在10000个元素的表中查找噢乖一个元素，该元素位于第2个。
经过多次折半，最终low 可能会是1，high可能是3. 1+3怎么等过等于集合长度了。
谢谢你提出。 我忘记说了，我说的情况时在 递增的时候他们low high 得和总是集合长度，
如果始终是 递减，则 无序考虑他的范围是在逐渐缩小。
至于具体的一个抽象过程 和 数学解释， 我还无法解释。
:) 谢谢你提出。 我忘记说了，我说的情况时在 递增的时候(初始状态时候的划分,)他们low high 得和总是集合长度，
如果始终是 递减，则 无序考虑他的范围是在逐渐缩小。
例如：1.2.3.4.5.6.7.8.9.10 = n ; low = 1; high = 10;key=7;
需要 7, 则
mid = (low + high) / 2 = 5
n < key ;
n =((low = mid + 1= 6 ) + high) / 2 = 8
n > key;
n = ((high = mid -1 = 7)+ low = 6) / 2 =7 ;
n == key
这个过程如果一开始递增的话，那么以后不管是再次的递增或递减他的low+high == n.length;
假如需要 3 则
mid = (low + high) / 2 = 5
n > key ;
n =((high = mid - 1= 4 ) + (low= 0)) / 2 = 2;
n < key;
n =((low= mid + 1= 3 ) + (high= 4)) / 2 = 3;
n == key;
至于具体的一个抽象过程 和 数学解释， 我还无法解释。
:) 再次修正：
这个算法就是 不断的缩小查找算法，不管是正向还是逆向（- or +）.
例如，
arr
low= 0,high = 9;
我要找7 ，哪么 即
mid = (low + high) /2;
mid = 5;
arr < 7
mid = (low = (mid + 1) + high) /2; // high不变，low = mid+1，因为根据上述条件则可知道arr肯定小于 7，则知道 low的范围肯定不包括 mid，所以 mid + 1；
arr > 7
mid = (low + high = mid - 1) /2;//low 不变，因为上述条件已经表明(我不知道该如何给出一个恰当的描述，但是应该很好理解，可惜我当时就是不理解，所以绕了很多弯路)。 high = mid- 1 是因为已经可以确定 当前状态下 的 arr 必定 大于7 。 哪么，现在的情形就是：
7 = arr
正确得到结果，结束。
我从中有两个认识。
1. 范围是在不断的缩小中的、
2.每次的 +1 or -1 是在不断的排除已经计算过的数.
啊，我觉得我明白了这个算法的原理和数学过程。 但是 我不能很清晰的将他表达出来。
:( 大家见谅..
才发现，单纯为了描述而描述是很没质量的，这个跟帖明显没有前几个好。 因为前几个是迫切的想求的知道和思路，而现在是已经明白了。 在描述的时候就不知道该如何表达了。
:)
页:
[1]
2