PHP实现找出有序数组中绝对值最小的数算法分析

网络编程 PHP编程 php技巧 分类:[default] 更新日期: 2016-11-13
这篇文章主要介绍了PHP实现找出有序数组中绝对值最小的数算法,简单分析了数组遍历及二分查找算法的相关操作技巧,需要的朋友可以参考下

本文实例讲述了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]即为绝对在最小的元素。

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相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《PHP数组(Array)操作技巧大全》

希望本文所述对大家PHP程序设计有所帮助。


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • Swift中内置的集合类型学习笔记
    Swift中内置的集合类型学习笔记
    Swift中自带数组.set.字典三大集合类型,这里将学习过程中的基础的Swift中内置的集合类型学习笔记进行整理,需要的朋友可以参考下一.引言 Swift中提供了3种集合类型,Array数据类型,Set集合类型,Dictionary字典类型.Array用于存放一组有序的数据,数据角标从0开始一次递增:Set用于存放一组无序的数据,数据不可以重复:Dicti ...
  • php项目开发中用到的快速排序算法分析
    这篇文章主要介绍了php项目开发中用到的快速排序算法,结合实例形式详细分析了php快速排序的原理与使用方法,需要的朋友可以参考下本文实例讲述了php项目开发中用到的快速排序算法.分享给大家供大家参考,具体如下: 实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算 ...
  • 将xml文件作为一个小的数据库,进行学生的增删改查的简单实例
    下面小编就为大家带来一篇将xml文件作为一个小的数据库,进行学生的增删改查的简单实例.小编觉得挺不错的,现在就分享给大家,也给大家做个参考.一起跟随小编过来看看吧1.xml文件: <?xml version="1.0" encoding="UTF-8"?><Students> <stude ...
  • 解读ASP.NET5&MVC6系列教程1:ASP.NET5简介
    这篇文章主要介绍ASP.NET 5简介以及对各个版本号进行解释,ASP.NET 5中新的变化,需要的朋友可以参考下.ASP.NET 5简介 ASP.NET 5是一个跨时代的改写,所有的功能和模块都进行了独立拆分,做到了彻底解耦.为了这些改写,微软也是蛮 拼的,几乎把.NET Framwrok全部改写了一遍,形成了一个.NET Core的东西. 在.NET C ...
  • ie9下关闭弹出窗口出现__flash__removeCallback未定义错误
    在关闭弹出窗口时,出现__flash__removeCallback未定义错误.而且是关了又出现,关于这个问题的解决方法如下使用swfupload作为上传组件,artdialog作为弹出窗口,在关闭弹出窗口时,出现"__flash__removeCallback"未定义错误.而且是关了又出现.网上有些解决方案,主要就是说覆写"_ ...
  • JavaScript中的正则表达式(推荐)
    正则表达式通常用于在文本中查找匹配的字符串,js正则表达式在程序开发中应用非常广泛,本文给大家介绍JavaScript 中的正则表达式推荐,感兴趣的朋友一起学习吧正则表达式的大致匹配过程是:依次拿出表达式和文本中的字符比较,如果每一个字符都能匹配,则匹配成功:一旦有匹配不成功的字符则匹配失败. 正则表达式通常用于在文本中查找匹配的字符串.Python里数量词 ...
猜你喜欢