PHP learning to count the frequency of a number appearing in a sorted array

The main content of this article is to use PHP to count the number of times a number appears in a sorted array. Interested friends can learn about it and hope it can help you.

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

Idea 1: General traversal, compare whether there are equal numbers, and automatically 1;

Idea 2: Use the dichotomy method to find the equal numbers first and record the subscripts. Then traverse from 0 to the subscript and record the total number of equals from the subscript to the beginning.

left=getLeft(data,k)
right=getRight(data,k)
retun right-left+1

getLeft data,k
    left=0
    right=arr.length-1
    mid=left+(right-left)/2
    while  left<=right
        if arr[mid]<k    //关键
            left=mid+1
        else
            right=mid-1
        mid=left+(right-left)/2
    return left
getRight data,k
    left=0
    right=arr.length-1
    mid=left+(right-left)/2 
    while  left<=right
        if arr[mid]<=k   //关键
            left=mid+1
        else
            right=mid-1
        mid=left+(right-left)/2
    return right

Related tutorials: PHP video tutorial

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