问题来源：http://androidguy.blog.51cto.com/974126/1129543
有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。

问题分解：

第一步：二分法寻找改变符号的位置（0视为正数）

第二步：比较位置左右数字的绝对值大小，取较小的那一个

1. <script language="javascript">  
2. var getBound = function(a,fr,to){  
3.     //[fr,to]是候选位置区间，位置从0开始计数  
4.     var b=fr,f=fr,t=to,s=true;  
5.     var left=function(b){return a[b-1];};//获取该位置右边的数字，增加代码可读性  
6.     var right=function(b){return a[b];};//获取该位置左边的数字，增加代码可读性  
7.     if(a.length===0){  
8.         return -1;//数组为空，返回-1  
9.     }else{  
10.         if(right(b)>=0){  
11.             s=false;//初始化位置就是要找的位置  
12.         }else{  
13.             for(var i=1;i<=100 && s;i++){  
14.                 b=f+Math.ceil((t-f)/2);//找到中点  
15.                 if(right(b)===undefined||(left(b)<0 && right(b)>=0)){  
16.                     s=false;//中点就是要找的位置  
17.                 }else if(right(b)<0){  
18.                     f=b;//下次前进找中点  
19.                 }else{  
20.                     t=b;//下次后退找中点  
21.                 }  
22.             }  
23.         }  
24.         return b;  
25.     }  
26. };  
27. var getMinAbs = function(a){  
28.     var b=getBound(a,0,a.length);//获取位置  
29.     if(b>=0){  
30.         if(b===0){  
31.             return Math.abs(a[b]);//位置在最左边  
32.         }else if(b===a.length){  
33.             return Math.abs(a[b-1]);//位置在最右边  
34.         }else{  
35.             return (Math.abs(a[b])>Math.abs(a[b-1])?Math.abs(a[b-1]):Math.abs(a[b]));//位置在中间  
36.         }  
37.     }else{  
38.         return false;  
39.     }  
40. };  
41.  
42. //测试代码  
43. var myArray=[-20,-13,-4,0,0,0,6,77,200,201,202];  
44. alert("[" + myArray + "]: " + getMinAbs(myArray));  
45. var myArray=[];  
46. alert("[" + myArray + "]: " + getMinAbs(myArray));  
47. var myArray=[-1];  
48. alert("[" + myArray + "]: " + getMinAbs(myArray));  
49. var myArray=[1];  
50. alert("[" + myArray + "]: " + getMinAbs(myArray));  
51. var myArray=[0,0];  
52. alert("[" + myArray + "]: " + getMinAbs(myArray));  
53. var myArray=[-1,-1];  
54. alert("[" + myArray + "]: " + getMinAbs(myArray));  
55. </script> 

 以myArray=[-20,-13,-4,0,0,0,6,77,200,201,202]为例，测试弹出：

 本文转自 hexiaini235 51CTO博客，原文链接：http://blog.51cto.com/idata/1131865，如需转载请自行联系原作者