2020-11-11：手写代码：如何获得有序数组中指定元素的个数？

福哥答案2020-11-11：

1.遍历法。无代码。
2.二分法。二分查找元素，然后二分查找左边界，再查找右边界，最后右边界减去左边界就是指定元素个数。这道题实际上是如下三道题的综合。

1. 在一个有序数组中，找某个数是否存在 。
2. 在一个有序数组中，找>=某个数最左侧的位置 。
3. 在一个有序数组中，找<=某个数最右侧的位置 。

golang代码如下：

package main

import "fmt"

func main() {
    arr := []int{0, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8}
    v := 3
    fmt.Println(v, "的个数是：", BSCount(arr, v))
}

//二分法
func BSCount(arr []int, v int) int {
    L := 0
    R := len(arr) - 1
    M := -1
    // L..R

    mid := -1
    //找目标值并且缩小左边界L和右边界R的范围
    for L <= R {
        mid = L + (R-L)>>1
        if arr[mid] == v {
            M = mid
            break
        } else if arr[mid] > v {
            R = mid - 1
        } else {
            L = mid + 1
        }
    }
    //没找到目标值，直接返回
    if M == -1 {
        return 0
    }

    index := 0
    LL := L //缓存原始左边界
    RR := R //缓存原始右边界

    //找左边界
    R = M //缩小范围
    for L <= R {
        mid = L + (R-L)>>1
        if arr[mid] >= v {
            index = mid
            R = mid - 1
        } else {
            L = mid + 1
        }
    }
    LL = index //左边界确定下来了
    R = RR     //原始右边界已经发生变化，需要恢复到以前的边界

    //找右边界
    L = M //缩小范围
    for L <= R {
        mid = L + (R-L)>>1
        if arr[mid] <= v {
            index = mid
            L = mid + 1
        } else {
            R = mid - 1
        }
    }
    RR = index //右边界确定下来了

    return RR - LL + 1
}

执行结果如下：

在这里插入图片描述

有疑问加站长微信联系（非本文作者）