【出自MT面试题】
难度系数：★★★☆☆ 被考察系数：★★★☆☆
题目描述：
有一个升序排列的数组，数组中可能有正数、负数或0，求数组中元素的绝对值最小的数。例如，数组{-10，-5，-2，7，15，50}，该数组中绝对值最小的数是-2。
分析与解答：
可以对数组进行顺序遍历，对每个遍历到的数求绝对值进行比较就可以很容易地找出数组中绝对值最小的数。本题中，由于数组是升序排列的，那么绝对值最小的数一定在正数与非正数的分界点处，利用这种方法可以省去很多求绝对值的操作。下面分别详细介绍这几种方法。
方法一：顺序比较法
最简单的方法就是从头到尾遍历数组元素，对每个数字求绝对值，然后通过比较就可以找出绝对值最小的数。
以数组{-10，-5，-2，7，15，50}为例，实现方式如下：
（1）首先遍历第一个元素-10，其绝对值为10，所以，当前最小值为min=10。
（2）遍历第二个元素-5，其绝对值为5，由于5＜10，因此，当前最小值min=5。
（3）遍历第三个元素-2，其绝对值为2，由于2＜5，因此，当前最小值为min=2。
（4）遍历第四个元素7，其绝对值为7，由于7＞2，因此，当前最小值min还是2。
（5）依此类推，直到遍历完数组为止就可以找出绝对值最小的数为-2。
示例代码如下：
程序的运行结果如下：
绝对值最小的数为：-2(www.xing528.com)
算法性能分析：
该方法的平均时间复杂度为O（N），空间复杂度为O（1）。
方法二：二分法
在求绝对值最小的数时可以分为如下三种情况：（1）如果数组第一个元素为非负数，那么绝对值最小的数肯定为数组第一个元素。（2）如果数组最后一个元素的值为负数，那么绝对值最小的数肯定是数组的最后一个元素。（3）如果数组中既有正数又有负数，首先找到正数与负数的分界点，如果分界点恰好为0，那么0就是绝对值最小的数。否则通过比较分界点左右的正数与负数的绝对值来确定最小的数。
那么如何来查找正数与负数的分界点呢？最简单的方法仍然是顺序遍历数组，找出第一个非负数（前提是数组中既有正数又有负数），接着通过比较分界点左右两个数的值来找出绝对值最小的数。这种方法在最坏的情况下时间复杂度为O（N）。下面主要介绍采用二分法来查找正数与负数的分界点的方法。主要思路是：取数组中间位置的值a[mid]，并将它与0值比较，比较结果分为以下3种情况：
（1）如果a[mid]==0，那么这个数就是绝对值最小的数。
（2）如果a[mid]＞0，a[mid-1]＜0，那么就找到了分界点，通过比较a[mid]与a[mid-1]的绝对值就可以找到数组中绝对值最小的数；如果a[mid-1]==0，那么a[mid-1]就是要找的数；否则接着在数组的左半部分查找。
（3）如果a[mid]＜0，a[mid+1]＞0，那么通过比较a[mid]与a[mid+1]的绝对值即可；如果a[mid+1]==0，那么a[mid+1]就是要查找的数。否则接着在数组的右半部分继续查找。
为了更好地说明以上方法，可以参考以下几个示例进行分析：
（1）如果数组为{1，2，3，4，5，6，7}，由于数组元素全部为正数，而且数组是升序排列，所以，此时绝对值最小的元素为数组的第一个元素1。
（2）如果数组为{-7，-6，-5，-4，-3，-2，-1}，此时数组长度length的值为7，由于数组元素全部为负数，而且数组是升序排列，所以，此时绝对值最小的元素为数组的第length-1个元素，该元素的绝对值为1。
（3）如果数组为{-7，-6，-5，-3，-1，2，4，}，此时数组长度length为7，数组中既有正数，也有负数，此时采用二分查找法，判断数组中间元素的符号。中间元素的值为-3，小于0，所以，判断中间元素后面一个元素的符号，中间元素后面的元素的值为-1小于0，因此，绝对值最小的元素一定位于右半部份数组{-1，2，4}中，继续在右半部分数组中查找，中间元素为2大于0，2前面一个元素的值为-1小于0，所以，-1与2中绝对值最小的元素即为所求的数组的绝对值最小的元素的值，所以，数组中绝对值最小的元素的值为-1。
实现代码如下：
算法性能分析：
通过上面的分析可知，由于采取了二分查找的方式，算法的平均时间复杂度得到了大幅降低，为O（log2N），其中，N为数组的长度。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
