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; }
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!