PHP counts the number of times a number appears in a sorted array

小云云
Release: 2023-03-19 14:24:01
Original
1870 people have browsed it

This article mainly introduces PHP's method of counting the number of occurrences of a number in a sorted array. It involves PHP's related operating skills for searching and counting in arrays based on the binary search algorithm. Friends who need it can refer to it. I hope it can help. Everyone.

Question

Count the number of times a number appears in a sorted array.

Solution

Since it is a sorted array, binary search is the most efficient. After you find it, expand it to both sides.

Code


##

<?php
function GetNumberOfK($data, $k)
{
  if(count($data)==0){
    return 0;
  }
  $index = 0;
  $low = 0;
  $high = count($data)-1;
  $middle = 0;
  //二分查找找到k的index
  while($low<=$high){
    $middle = ($high+$low)>>1;
    if($data[$middle]==$k){
      $index = $middle;
      break;
    }
    else if($data[$middle]>$k) {
      $high = $middle -1;
    }else{
      $low = $middle+1;
    }
    $index = -1;
  }
  // console.log(index);
  // 如果没找到
  if($index==-1){
    return 0;
  }
  //找到了 分别往左右查找边界
  $start = $index;
  $end = $index;
  $count = 0;
  while($data[$start]==$k){
    $count++;
    $start--;
  }
  while($data[$end]==$k){
    $count++;
    $end++;
  }
  return $count-1;
}
Copy after login

Related recommendations:


Problems related to user-defined sorted array

In the sorted array, find the number of occurrences of a given number. For example, in [1, 2, 2, 2, 3]

Reorder the array according to a certain key value

The above is the detailed content of PHP counts the number of times a number appears in a sorted array. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template