思路

本道題有好幾種解法
1.直接遍歷數(shù)組，判斷前后的值是否相同，找到元素開始位置和結(jié)束位置，時間復(fù)雜度O(n)
2.使用二分查找找到目標(biāo)值，在向前向后遍歷，找到所有的數(shù)，比上面略優(yōu)，時間復(fù)雜度也是O(n)
3.使用二分查找分別找到第一個目標(biāo)值出現(xiàn)的位置和最后一個位置，時間復(fù)雜度O(logn)

在排序數(shù)組中找元素，首先考慮使用二分查找

下面是使用二分查找在數(shù)組中尋找某個數(shù)

        function binarySearch(data, arr, start, end) {
            if (start > end) {
                return -1;
            }
            var mid = Math.floor((end + start) / 2);
            if (data == arr[mid]) {
                return mid;
            } else if (data < arr[mid]) {
                return binarySearch(data, arr, start, mid - 1);
            } else {
                return binarySearch(data, arr, mid + 1, end);
            }
        }

找到第一次和最后一次出現(xiàn)的位置我們只需要對上面的代碼進行稍加的變形
第一次位置：找到目標(biāo)值，并且前一位的數(shù)字和當(dāng)前值不相等
最后一次位置：找到目標(biāo)值，并且后一位的數(shù)字和當(dāng)前值不相等

    function GetNumberOfK(data, k) {
      if (data && data.length > 0 && k != null) {
        const firstIndex = getFirstK(data, 0, data.length - 1, k);
        const lastIndex = getLastK(data, 0, data.length - 1, k);
        if (firstIndex != -1 && lastIndex != -1) {
          return lastIndex - firstIndex + 1;
        }
      }
      return 0;
    }

    function getFirstK(data, first, last, k) {
      if (first > last) {
        return -1;
      }
      const mid = parseInt((first + last) / 2);
      if (data[mid] === k) {
        if (data[mid - 1] != k) {
          return mid;
        } else {
          return getFirstK(data, first, mid-1, k);
        }
      } else if (data[mid] > k) {
        return getFirstK(data, first, mid - 1, k);
      } else if (data[mid] < k) {
        return getFirstK(data, mid + 1, last, k);
      }
    }

    function getLastK(data, first, last, k) {
      if (first > last) {
        return -1;
      }
      const mid = parseInt((first + last) / 2);
      if (data[mid] === k) {
        if (data[mid + 1] != k) {
          return mid;
        } else {
          return getLastK(data, mid + 1, last, k);
        }
      } else if (data[mid] > k) {
        return getLastK(data, first, mid - 1, k);
      } else if (data[mid] < k) {
        return getLastK(data, mid + 1, last, k);
      }
    }