本文实例讲述了PHP实现找出有序数组中绝对值最小的数算法。分享给大家供大家参考,具体如下:
问题:
一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值。
方法1:
遍历数组,找到绝对值最小值,时间复杂度O(n),n为元素个数。
方法2:
二分查找,因为数组有序,可以利用二分查找,时间复杂度O(logn)。
分析步骤:
1. 如果第一个数为正数,说明整个数组没有负数,直接返回第一个数
2. 如果最后一个数为负数,说明整个数组没有正数,直接返回最后一个数
3. 数组元素有正有负,说明绝对值最小的元素肯定在正负数交界处,需要二分查找上场:
①. 如果a[mid]<0,因为数组是升序,说明绝对值最小的数不会出现在a[mid]左边,同时判断a[mid+1]元素的正负,如果为负数,那么需要在mid右侧区间进行查找,如果a[mid-1]不为负,那么说明这两个数是数组中正负交界点,返回这两个数的绝对值较小的。
②. 如果a[mid]>0,因为数组是升序,说明绝对值最小的数不会出现在a[mid]右边,同时判断a[mid-1]元素的正负,如果为负数,那么说明这两个数是数组中正负交界点,返回这两个数的绝对值较小的,如果a[mid-1]不为负,那么需要在mid以左的区间进行查找。
③. 如果a[mid] == 0,那么a[mid]即为绝对在最小的元素。
?
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
|
function selectAbsMinNum( array $arr )
{
$start = 0;
$len = count ( $arr ) - 1;
if ( $arr [0] > 0) { //正数数组
return $arr [0];
}
if ( $arr [ $len ] < 0) { //负数数组
return $arr [ $len ];
}
while ( $start < $len ) {
$mid = floor (( $start + $len ) / 2);
if ( $arr [ $mid ] > 0) {
if ( $arr [ $mid - 1] > 0) {
$len = $mid - 1;
} else {
return min( $arr [ $mid ], - $arr [ $mid - 1]);
}
} elseif ( $arr [ $mid ] < 0) {
if ( $arr [ $mid + 1] < 0) {
$start = $mid + 1;
} else {
return min(- $arr [ $mid ], $arr [ $mid + 1]);
}
} else {
return $arr [ $mid ];
}
}
}
$sortArr = [-5, -4, -4, -4, 5, 7, 9];
echo selectAbsMinNum( $sortArr ), PHP_EOL;
|
运行结果:4
希望本文所述对大家PHP程序设计有所帮助。
相关文章
猜你喜欢
- ASP.NET自助建站系统的域名绑定与解析教程 2025-06-10
- 个人服务器网站搭建:如何选择合适的服务器提供商? 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持? 2025-06-10
- 64M VPS建站:如何选择最适合的网站建设平台? 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法? 2025-06-10
TA的动态
- 2025-07-10 怎样使用阿里云的安全工具进行服务器漏洞扫描和修复?
- 2025-07-10 怎样使用命令行工具优化Linux云服务器的Ping性能?
- 2025-07-10 怎样使用Xshell连接华为云服务器,实现高效远程管理?
- 2025-07-10 怎样利用云服务器D盘搭建稳定、高效的网站托管环境?
- 2025-07-10 怎样使用阿里云的安全组功能来增强服务器防火墙的安全性?
快网idc优惠网
QQ交流群
您的支持,是我们最大的动力!
热门文章
-
2025-05-27 73
-
2025-05-25 73
-
2025-06-04 13
-
2025-05-25 91
-
2025-05-29 97
热门评论