二分查找算法 得一些疑惑。

zong

先来一个code section define int[] arr = {low..high},low=0,high=arr.length - 1 ,mid = 0,key= n; while(low <= high) { mid = (low + high) / 2; //每次去区间的中间索引。 if(arr[mid] == key) return mid; //恰好相等，则直接返回 mid if(arr[mid] > key) high = mid - 1; //当前索引数据大于key,则知道,key必然在 arr[low .. mid - 1]中，这个时候low不变，high = mid - 1; if(arr[mid] < key) low = mid + 1; //当然索引数据小与key ,则知道,key必然在arr[mid + 1 .. high]中，这个时候high 不便。low= mid +1; } //找不到 -1 return -1; 用公式给出则： mid = arr[low .. high / 2]; key < arr[low .. high -1]; key > arr[low + 1.. high ]; 如果思路按照这个走下去， 发现这个算法很有意思， 至少我感觉就很爽。 例如 有这么一个序列： 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， 这样子就会陷入一种循环中去了。 实际上，写道这里，可能各位朋友还不知道我想表达什么意思。 我主要是对于这样一个推力过程感到困惑，抽象思维太弱。 各位可以给出一个严谨的推理过程么？ 还有，二分查找算法 主要用于什么地方？ 我数学基础很差， 以前一直逃避算法 这些东西，觉得自己搞不定。 例如这个程序，我现在也大致知道他的原理和用法，但是对于其内部的一个抽象过程，我很迷糊， 这样，要不多长时间我可能就忘记了。 只有真正明白了 内在，才是真正掌握了这个算法。 而且，我发现这个算法思维过程在现实世界中也能找到很多对应。 我想这就是数学的美丽把？ 我最近对数学 极为感兴趣。 觉得每天最爽的消磨时间就是找一个算法，然后去找他的内在机理。 这个算法也是我在研究顺序插入排序的时候 突然冒出来的想法， 这样子就可以每次减少一倍的查询时间. 我没有受过专业的科学训练. 所以在描述和思维上还请见谅.

medie2005

在计算机的实现中，整数‘/’是按下取整来操作的，不是按四舍五入。

仙剑魔

简单来说,是否四舍五入是可以人为控制的

无心人

具体如何结束在你的算法控制

zong

各位，谢谢回复. 不过，我想了解的是这样一个推理过程的数学描述？！ 就是数学规则， 一种抽象过程。 我自己稍微有个想法， 今天吃饭回来时突然想出来的，那就是不管 low .. high 得位置如何变化， 他们的和都是 这个集合的长度. 我现在还在公司，没经历去思考，今天晚上整理写思路，再求证下。 我觉得各位可能觉得这个算法实在简单？ 我想要这个算法背后的一个具体的数学推理过程，也就是抽象过程。

liangbch

不对呀，如果在10000个元素的表中查找噢乖一个元素，该元素位于第2个。 经过多次折半，最终low 可能会是1，high可能是3. 1+3怎么等过等于集合长度了。

zong

原帖由 liangbch 于 2008-12-15 16:53 发表 不对呀，如果在10000个元素的表中查找噢乖一个元素，该元素位于第2个。 经过多次折半，最终low 可能会是1，high可能是3. 1+3怎么等过等于集合长度了。

谢谢你提出。 我忘记说了，我说的情况时在 递增的时候他们low high 得和总是集合长度， 如果始终是 递减，则 无序考虑 他的范围是在逐渐缩小。 至于具体的一个抽象过程 和 数学解释， 我还无法解释。

无心人

zong

谢谢你提出。 我忘记说了，我说的情况时在 递增的时候(初始状态时候的划分,)他们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[mid] < key ; n[mid + 1 .. high] = ((low = mid + 1 = 6 ) + high) / 2 = 8 n[mid] > key; n[mid + 1 .. high - 1] = ((high = mid -1 = 7) + low = 6) / 2 = 7 ; n[mid] == key 这个过程如果一开始递增的话，那么以后不管是再次的递增或递减他的low+high == n.length; 假如需要 3 则 mid = (low + high) / 2 = 5 n[mid] > key ; n[low .. high - 1] = ((high = mid - 1 = 4 ) + (low = 0)) / 2 = 2; n[mid] < key; n[low + 1 .. high] = ((low= mid + 1 = 3 ) + (high = 4)) / 2 = 3; n[mid] == key; 至于具体的一个抽象过程 和 数学解释， 我还无法解释。

zong

再次修正： 这个算法就是 不断的缩小查找算法，不管是正向还是逆向（- or +）. 例如， arr[1.2.3.4.5.6.7.8.9.10] low = 0,high = 9; 我要找7 ，哪么 即 mid = (low + high) /2; mid = 5; arr[mid] < 7 mid = (low = (mid + 1) + high) /2; // high不变，low = mid+1，因为根据上述条件则可知道arr[mid]肯定小于 7 ，则知道 low的范围肯定不包括 mid，所以 mid + 1； arr[mid] > 7 mid = (low + high = mid - 1) /2;//low 不变，因为上述条件已经表明(我不知道该如何给出一个恰当的描述，但是应该很好理解，可惜我当时就是不理解，所以绕了很多弯路)。 high = mid - 1 是因为已经可以确定 当前状态下 的 arr[mid] 必定 大于7 。 哪么，现在的情形就是： 7 = arr[low + (mid - 1) / 2] 正确得到结果，结束。 我从中有两个认识。 1. 范围是在不断的缩小中的、 2.每次的 +1 or -1 是在不断的排除已经计算过的数. 啊，我觉得我明白了这个算法的原理和数学过程。 但是 我不能很清晰的将他表达出来。 大家见谅.. 才发现，单纯为了描述而描述是很没质量的，这个跟帖明显没有前几个好。 因为前几个是迫切的想求的知道和思路，而现在是已经明白了。 在描述的时候就不知道该如何表达了。