這篇文章主要介紹了PHP實作找出有序數組中絕對值最小的數演算法,簡單分析了數組遍歷及二分查找演算法的相關操作技巧,需要的朋友可以參考下
本文實例講述了PHP實作找出有序數組中絕對值最小的數演算法。分享給大家供大家參考,具體如下:
問題:
#一個有序數組,有可能有負值,也有可能沒有,現需要找出其中絕對值最小的值。
方法1:
遍歷數組,找出絕對值最小值,時間複雜度O(n),n為元素個數。
方法2:
二分查找,因為陣列有序,可以利用二分查找,時間複雜度O(logn)。
分析步驟:
1. 若第一個數為正數,表示整個陣列沒有負數,直接傳回第一個數
2. 如果最後一個數字為負數,表示整個數組沒有正數,直接回傳最後一個數
3. 數組元素有正有負,表示絕對值最小的元素肯定在正負數交界處,需要二分找出上場:
①. 如果a[mid]3e17e771187c0c1f5ea1981de93eb79d0,因為陣列是升序,表示絕對值最小的數不會出現在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中文網其他相關文章!