PHP explains how to count the number of occurrences of a number in a sorted array

This article mainly introduces PHP's method of counting the number of occurrences of a number in a sorted array, involving 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

The example of this article describes the method of PHP to count the number of occurrences of a number in a sorted array. Share it with everyone for your reference, the details are as follows:

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. Once 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;
}

PS: Here again for everyone Recommend 2 statistical tools (JS implementation) with similar functions for your reference:

Online word count statistics tool:
http ://tools.jb51.net/code/zishutongji

Online character statistics and editing tool:
http://tools.jb51.net/ code/char_tongji

Articles you may be interested in:

PHP calls ffmpeg to take video screenshots and splice the script

Detailed explanation of scenarios and verification rules in Yii2

Summary of concurrency stress testing of MixPHP, Yii and CodeIgniter

The above is the detailed content of PHP explains how to count the number of occurrences of a number in a sorted array. For more information, please follow other related articles on the PHP Chinese website!