поиск отсортированного массива в C

Question

Я работаю над проблемой в C, и у меня есть быстрый вопрос об этом. Проблема в следующем: мне дан некоторый отсортированный массив целых чисел, скажем, a[i] = { 1, 2, 3, 3, 3 }. Теперь я должен запустить программу, которая ищет заданное целое число, возвращает местоположение первого вхождения и количество вхождений этого целого в массиве.

Итак, если бы я искал 3, то у меня было бы первое вхождение в a[2], и есть три вхождения 3. Для первой части поиска первого вхождения я могу просто использовать strcspn из файла заголовка строки. Однако, для второй части, есть ли встроенная функция, которая будет подсчитывать количество экземпляров конкретного целого числа?

На самом деле я могу сделать это своими «голыми руками», просто увеличив переменную счетчика. Однако мой профессор дал мне подсказку, что тип возвращаемого значения должен быть size_t, предлагая использовать некоторые встроенные функции. Любая помощь будет оценена.

Спасибо, Александр

Answer 1

Нет, для этого нет стандартной функции. Ваш профессор сказал, что тип возвращаемого значения должен быть size_t, потому что это стандартный тип, используемый при подсчете размеров или количества объектов в памяти. Тип unsigned int может быть недостаточно большим в некоторых системах.

Answer 2

Ища x, вы можете использовать бинарный поиск, чтобы найти первое вхождение x и найти первое вхождение любого целого числа больше x (или конца массива), используя различные условия для установки левой и правой сторон. вашего окна поиска.

Простой бинарный поиск в псевдокоде:

left,right = 0, n

while right - left > 1
  mid = left + right / 2
  if array[mid] < x
    left = mid
  else
    right = mid

То, что вам нужно изменить, это то, если вы решаете, вводить ли левую или правую часть окна поиска. Если у вас есть два поиска, один, чтобы найти левую часть последовательности x-es и один, чтобы найти правую сторону, тогда разница между этими двумя является количеством записей.

Answer 3

Подсказка : Поскольку данный массив уже отсортирован, вы можете использовать Бинарный поиск, чтобы найти экземпляр заданного целого числа, идти назад, пока не найдете первый случай, затем увеличивать позицию до тех пор, пока больше не будет совпадений. 1003 *

Answer 4

Использование переменной size_t в качестве счетчика будет работать. Но лучший подход - найти один из экземпляров, используя бинарный поиск (для этого есть библиотечная функция) и оттуда искать вперед и назад.

Answer 5

Я не думаю, что strcspn поможет - он работает со строкой (массивом символов), но вы говорите, что у вас есть массив целых чисел.Другие уже сказали, что еще я собирался сказать.