PHP의 정렬된 배열에서 절대값이 가장 작은 숫자를 찾는 알고리즘을 구현하는 방법

이 글은 정렬된 배열에서 절대값이 가장 작은 숫자를 찾는 알고리즘의 PHP 구현을 주로 소개하고, 배열 순회 및 이진 검색 알고리즘의 관련 운영 기술을 간략하게 분석합니다. 도움이 필요한 친구들은 참고할 수 있습니다. 기사에서는 예제와 함께 PHP 구현을 설명합니다. 순서가 지정된 배열에서 절대값이 가장 작은 숫자를 찾습니다. 참조용으로 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

질문: 순서 있는 배열, 값은 음수 값을 가질 수도 있고 그렇지 않을 수도 있습니다. 이제 우리는 가장 작은 절대값을 가진 값을 찾아야 합니다. .

방법 1:

배열을 탐색하여 최소 절대값을 찾습니다. 시간 복잡도는 O(n)이고 n은 요소 수입니다.

방법 2:

이진 검색, 배열이 정렬되어 있으므로 이진 검색을 사용할 수 있으며 시간 복잡도는 O(logn)입니다.

분석 단계: 1. 첫 번째 숫자가 양수이면 전체 배열에 음수가 없다는 의미이며 첫 번째 숫자가 직접 반환됩니다.

2. , 이는 전체 배열 번호에 양수가 없다는 의미이며, 마지막 숫자를 직접 반환합니다

3. 배열 요소는 양수와 음수이므로 절대값이 가장 작은 요소가 양수와 음수의 교차점에 있어야 함을 의미합니다. 음수, 이진 검색이 필요합니다:

① a[mid]<0인 경우 배열이 오름차순이므로 절대값이 가장 작은 숫자가 a[의 왼쪽에 나타나지 않습니다. mid]와 동시에 a[mid+1]의 요소가 양수인지 음수인지 확인합니다. 그러면 mid의 오른쪽 간격에서 검색해야 합니다. -1]이 음수가 아닌 경우 이는 이 두 숫자가 배열의 양수와 음수의 교차점이며 두 숫자의 절대값이 더 작다는 것을 의미합니다.

②. a[mid]>0이면 배열이 오름차순이므로 a[mid]의 오른쪽에는 절대값이 가장 작은 숫자가 나타나지 않음을 의미합니다. a[mid-1]의 요소가 양수인지 음수인지 여부. 음수이면 이 두 숫자가 배열에서 양수와 음수의 교차점이며 두 숫자의 절대값이 더 작음을 의미합니다. a[mid-1]이 음수가 아닌 경우 mid의 왼쪽 간격에서 검색해야 합니다.

3. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!