[문제]

정렬이 되어 있으면서 / 중복이 가능한 / 갯수(n)가 많은 배열이 있다. 임의의 수 k가 주어 졌을 때 배열 안에 k가 몇개가 있는지 알아 내는 함수를 만들어라.

#include <iostream>
using namespace std;

typedef int val; // value
typedef int idx; // index
static const idx INVALID_INDEX = -1;

idx getLeftIndex(val* arr, idx l, idx r, int k)
{
  while (l <= r)
  {
    idx p = (l + r) / 2; // pivot
    if (arr[p] == k)
    {
      if (p == l) return p;
      if (arr[p - 1] < k) return p;
      r = p - 1;
    } else
    if (arr[p] < k) l = p + 1;
    else r = p - 1; // arr[p] > k
  }
  return INVALID_INDEX;
}

idx getRightIndex(val* arr, idx l, idx r, int k)
{
  while (l <= r)
  {
    idx p = (l + r) / 2; // pivot
    if (arr[p] == k)
    {
      if (p == r) return p;
      if (arr[p + 1] > k) return p;
      l = p + 1;
    } else
    if (arr[p] < k) l = p + 1;
    else r = p - 1; // arr[p] > k
  }
  return INVALID_INDEX;
}

int getCount(val* arr, int n, val k)
{
  int lIndex = getLeftIndex(arr, 0, n - 1, k);
  if (lIndex == INVALID_INDEX) return 0;
  int rIndex = getRightIndex(arr, 0, n - 1, k);
  if (lIndex == INVALID_INDEX) return 0;
  return rIndex - lIndex + 1;
}

void test1()
{
  val arr[] = { 1, 2, 3, 4, 5, 5, 5, 7, 8, 9 };
  int c = getCount(arr, sizeof(arr) / sizeof(val), 5);
  cout << c << endl;
}

void test2()
{
  val arr[] = { 5, 5, 5, 5, 5, 5, 5, 7, 8, 9};
  int c = getCount(arr, sizeof(arr) / sizeof(val), 5);
  cout << c << endl;
}

void test3()
{
  val arr[] = { 1, 2, 3, 5, 5, 5, 5, 5, 5, 5};
  int c = getCount(arr, sizeof(arr) / sizeof(val), 5);
  cout << c << endl;
}

int main()
{
  test1();
  test2();
  test3();
}

[소스 코드]

getcount.zip