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

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 是在不断的排除已经计算过的数.

啊，我觉得我明白了这个算法的原理和数学过程。 但是 我不能很清晰的将他表达出来。

    大家见谅..

才发现，单纯为了描述而描述是很没质量的，这个跟帖明显没有前几个好。 因为前几个是迫切的想求的知道和思路，而现在是已经明白了。 在描述的时候就不知道该如何表达了。