How to implement the algorithm of finding the number with the smallest absolute value in an ordered array in PHP

This article mainly introduces the PHP algorithm for finding the number with the smallest absolute value in an ordered array, and briefly analyzes the related operating skills of array traversal and binary search algorithms. Friends in need can refer to it

The example in this article describes the PHP algorithm for finding the number with the smallest absolute value in an ordered array. Share it with everyone for your reference, the details are as follows:

Question:

An ordered array, the value may have negative value, or it may No, now we need to find the value with the smallest absolute value.

Method 1:

Traverse the array and find the absolute minimum value. The time complexity is O(n), n is the number of elements.

Method 2:

Binary search, because the array is ordered, you can use binary search, the time complexity is O (logn).

Analysis steps:

1. If the first number is a positive number, it means there are no negative numbers in the entire array, and the first number is returned directly

2. If the last number is a negative number, it means that there is no positive number in the entire array, and the last number will be returned directly

3. If the array elements are positive or negative, it means that the element with the smallest absolute value must be in At the junction of positive and negative numbers, binary search is required:

①. If a[mid]<0, because the array is in ascending order, it means that the number with the smallest absolute value will not appear on the left side of a[mid], and at the same time Determine whether the element a[mid+1] is positive or negative. If it is a negative number, you need to search in the interval on the right side of mid. If a[mid-1] is not negative, it means that these two numbers are the positive and negative intersection points in the array. , returns the smaller absolute value of the two numbers.

②. If a[mid]>0, because the array is in ascending order, it means that the number with the smallest absolute value will not appear on the right side of a[mid], and at the same time determine the positive or negative of the element a[mid-1] , if it is a negative number, it means that these two numbers are the positive and negative intersection points in the array, and the absolute value of the two numbers is smaller. If a[mid-1] is not negative, then it needs to be in the interval to the left of mid. Find it.

③. If a[mid] == 0, then a[mid] is the absolute smallest element.

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;

Run result: 4

The above is the detailed content of How to implement the algorithm of finding the number with the smallest absolute value in an ordered array in PHP. For more information, please follow other related articles on the PHP Chinese website!