document.write('
可以对数组进行顺序遍历,对每个遍历到的数求绝对值进行比较就可以很容易地找出数组中绝对值最小
的数。本题中,由于数组是升序排列的,那么绝对值最小的数一定在正数与非正数的分界点处,利用这
种方法可以省去很多求绝对值的操作。下面分别详细介绍这几种方法。
方法一:顺序比较法
最简单的方法就是从头到尾遍历数组元素,对每个数字求绝对值,然后通过比较就可以找出绝对值最
小的数。
以数组[-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。
示例代码如下:
def findMin(array):
if array==Noneorlen(array)<=0:
print "输入参数不合理"
return 0
mins=2**32
i=0
while i<len(array):
if abs(array[i])<abs(mins):
mins=array[i]
i+=1
return mins
if __name__=="__main__":
arr=[-10, -5, -2, 7, 15, 50]
print "绝对值最小的数为: "+str(findMin(arr))
程序的运行结果为:
绝对值最小的数为:-2
算法性能分析:
该方法的平均时间复杂度为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。
实现代码如下:
def findMin(array):
if array==None or len(array)<=0:
print "输入参数不合理";
return 0;
lens=len(array)
#数组中没有负数
if array[0]>=0:
return array[0];
#数组中没有正数
if array[lens-1]<=0:
return array[lens-1];
mid=0;
begin=0;
end=lens-1;
absMin=0;
#数组中既有正数又有负数
while True:
mid=begin+(end-begin)/2;
#如果等于0, 那么就是绝对值最小的数
if array[mid]==0:
return 0; #如果大于0, 正负数的分界点在左侧
elif array[mid]>0:
#继续在数组的左半部分查找
if array[mid-1]>O:
end=mid-1;
elif array[mid-1]==0:
return 0;
#找到正负数的分界点
else:
break;# 如果小于0, 在数组右半部分查找
else:
#在数组右半部分继续查找
if array[mid+1]<0:
begin=mid+1
elif array[mid+1]==O:
return 0;
#找到正负数的分界点
else:
break;
#获取正负数分界点处绝对值最小的值
if (array[mid]>0):
if array[mid]<abs(array[mid-1]):
absMin=array[mid];
else:
absMin=array[mid-1];
else:
if abs(array[mid])<array[mid+1]:
absMin=array[mid];
else:
absMin=array[mid+1];
return absMin;
if __name__="__main__":
arr=[-10, -5, -2, 7, 15, 50]
print "绝Xt值最小的数为: "+str(findMin(arr))
算法性能分析:
通过上面的分析可知,由于采取了二分查找的方式,算法的平均时间复杂度得到了大幅降低,为
O(log2
N),其中,N为数组的长度。
');