buscando una matriz ordenada en C

Estoy trabajando en un problema en C, y tengo una pregunta rápida al respecto. El problema es el siguiente: me dan una serie ordenada de enteros, por ejemplo, a[i] = { 1, 2, 3, 3, 3 } . Ahora, se supone que debo ejecutar un progtwig que busque un número entero dado, devuelve la ubicación de la primera aparición y el número de apariciones de ese número entero en la matriz.

Por lo tanto, si estuviera buscando 3 , tendría la primera aparición en a[2] y hay tres apariciones de 3 . Para la primera parte, de encontrar la primera aparición, simplemente puedo usar strcspn del archivo de encabezado de cadena. Sin embargo, para la segunda parte, ¿hay una función incorporada que contaría el número de instancias de un entero particular?

Realmente puedo hacer esto con mis “manos vacías” simplemente incrementando una variable de contador. Sin embargo, mi profesor me dio una pista de que el tipo de retorno debería ser size_t, sugiriendo que se podrían usar algunas funciones incorporadas. Cualquier ayuda sería apreciada.

Gracias alexander

No, no hay una función estándar para hacer esto. Su profesor dijo que el tipo de retorno debería ser size_t porque ese es el tipo estándar a usar cuando se cuentan tamaños o números de objetos en la memoria. El tipo “unsigned int” podría no ser lo suficientemente grande en algunos sistemas.

Al buscar x, puede usar la búsqueda binaria para encontrar la primera aparición de x y encontrar la primera aparición de cualquier entero más grande que x (o el final de la matriz) utilizando diferentes condiciones para configurar los lados izquierdo y derecho de su búsqueda ventana.

Una simple búsqueda binaria en pseudo código:

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

Lo que debe cambiar aquí es si decide si traer el lado izquierdo o derecho de la ventana de búsqueda. Si tiene dos búsquedas, una para encontrar el lado izquierdo de la secuencia de x-es y otra para encuentra el lado derecho, entonces la diferencia entre estos dos es el número de entradas.

Sugerencia : ya que la matriz dada ya está ordenada, puede usar la Búsqueda binaria para encontrar una instancia del entero dado, caminar hacia atrás hasta encontrar la primera aparición, luego incrementar la posición hasta que no haya más coincidencias.

No creo que strcspn vaya a ayudar, funciona en una cadena (matriz de caracteres), pero dices que tienes una serie de entradas. Otros ya han dicho lo que iba a decir.

Usar una variable de size_t como el contador funcionaría. Pero un mejor enfoque es encontrar una de las instancias utilizando una búsqueda binaria (hay una función de biblioteca para esto) y buscar hacia adelante y hacia atrás desde allí.