百度面试题：求绝对值最小的数

有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现

例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。

算法实现的基本思路

找到负数和正数的分界点，如果正好是0就是它了，如果是正数，再和左面相邻的负数绝对值比较，如果是负数，取取绝对值与右面正数比较。还要考虑数组只有正数或负数的情况。

我根据这个思路用Java简单实现了一个算法。大家有更好的实现方法欢迎跟帖

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

<code>public</code> <code>class</code> <code>MinAbsoluteValue</code>

<code>{</code>

<code>    </code><code>private</code> <code>static</code> <code>int</code> <code>getMinAbsoluteValue(</code><code>int</code><code>[] source)</code>

<code>    </code><code>{</code>

<code>        </code> 

<code>        </code><code>int</code> <code>index = </code><code>0</code><code>;</code>

<code>        </code><code>int</code> <code>result = </code><code>0</code><code>; </code>

<code>        </code><code>int</code> <code>startIndex = </code><code>0</code><code>;</code>

<code>        </code><code>int</code> <code>endIndex = source.length - </code><code>1</code><code>;</code>

<code>        </code><code>//  计算负数和正数分界点</code>

<code>        </code><code>while</code><code>(</code><code>true</code><code>)</code>

<code>        </code><code>{&lt;br&gt;                </code><code>//  计算当前的索引</code>

<code>            </code><code>index = startIndex + (endIndex - startIndex) / </code><code>2</code><code>;</code>

<code>            </code><code>result = source[index];&lt;br&gt;                </code><code>//  如果等于0，就直接返回了，0肯定是绝对值最小的</code>

<code>            </code><code>if</code><code>(result==</code><code>0</code><code>)</code>

<code>            </code><code>{</code>

<code>                </code><code>return</code> <code>0</code><code>;</code>

<code>            </code><code>}&lt;br&gt;                </code><code>//  如果值大于0，处理当前位置左侧区域，因为负数肯定在左侧</code>

<code>            </code><code>else</code> <code>if</code><code>(result &gt; </code><code>0</code><code>)</code>

<code>                </code><code>if</code><code>(index == </code><code>0</code><code>)</code>

<code>                </code><code>{</code>

<code>                    </code><code>break</code><code>;</code>

<code>                </code><code>}</code>

<code>                </code><code>if</code><code>(source[index-</code><code>1</code><code>] &gt;</code><code>0</code><code>)</code>

<code>                    </code><code>endIndex = index - </code><code>1</code><code>;</code>

<code>                </code><code>else</code> <code>if</code><code>(source[index-</code><code>1</code><code>] ==</code><code>0</code><code>)</code>

<code>                    </code><code>return</code> <code>0</code><code>;</code>

<code>                </code><code>else</code>

<code>            </code><code>}&lt;br&gt;                </code><code>//  如果小于0，处理当前位置右侧的区域，因为正数肯定在右侧的位置</code>

<code>            </code><code>else</code>

<code>                </code><code>if</code><code>(index == endIndex)</code>

<code>                </code><code>if</code><code>(source[index + </code><code>1</code><code>] &lt; </code><code>0</code><code>)</code>

<code>                    </code><code>startIndex = index + </code><code>1</code><code>;</code>

<code>                </code><code>else</code> <code>if</code><code>(source[index + </code><code>1</code><code>] == </code><code>0</code><code>)</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>//  根据分界点计算绝对值最小的数</code>

<code>        </code><code>if</code><code>(source[index] &gt; </code><code>0</code><code>)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(index == </code><code>0</code> <code>|| source[index] &lt; Math.abs(source[index-</code><code>1</code><code>]))</code>

<code>                </code><code>result= source[index];</code>

<code>                </code><code>result = source[index-</code><code>1</code><code>];</code>

<code>        </code><code>else</code>

<code>            </code><code>if</code><code>(index == source.length - </code><code>1</code> <code>|| Math.abs(source[index]) &lt; source[index+</code><code>1</code><code>])</code>

<code>                </code><code>result = source[index+</code><code>1</code><code>];</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) </code><code>throws</code> <code>Exception</code>

<code>        </code><code>int</code><code>[] arr1 = </code><code>new</code> <code>int</code><code>[]{-</code><code>23</code><code>,-</code><code>22</code><code>,-</code><code>3</code><code>,-</code><code>2</code><code>,</code><code>1</code><code>,</code><code>2</code><code>,</code><code>3</code><code>,</code><code>5</code><code>,</code><code>20</code><code>,</code><code>120</code><code>};</code>

<code>        </code><code>int</code><code>[] arr2 = </code><code>new</code> <code>int</code><code>[]{-</code><code>23</code><code>,-</code><code>22</code><code>,-</code><code>12</code><code>,-</code><code>6</code><code>,-</code><code>4</code><code>};</code>

<code>        </code><code>int</code><code>[] arr3 = </code><code>new</code> <code>int</code><code>[]{</code><code>1</code><code>,</code><code>22</code><code>,</code><code>33</code><code>,</code><code>55</code><code>,</code><code>66</code><code>,</code><code>333</code><code>};</code>

<code>        </code><code>int</code> <code>value = getMinAbsoluteValue(arr1);</code>

<code>        </code><code>System.out.println(value);</code>

<code>        </code><code>value = getMinAbsoluteValue(arr2);</code>

<code>        </code><code>value = getMinAbsoluteValue(arr3);</code>

<code>}</code>

 上面的代码分别输出1、-4和1

本文转自银河使者博客园博客，原文链接http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html如需转载请自行联系原作者

银河使者