Thread: finde closest in teh array

(sorry for the spelling errors in the title)
Hi,

I have a problem. So, I have this array (assume sorted) and i need to find out the closest upper value for any input int. Example:

Code:

/* bsearch example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int keys[] = {2, 5, 7, 12, 34, 44, 46, 51, 57, 67, 73, 83, 92, 100};


int main ()
{
  int * pItem;
  int a = 4;
  int b = 44;
  int c = 46;
  int d = 8;
  int e = 83;
  int f = 100;
  int g = 35;
  pItem = (int*) bsearch (&a, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",a);
    
  pItem = (int*) bsearch (&b, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",b);
    
  pItem = (int*) bsearch (&c, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",c);
    
  pItem = (int*) bsearch (&d, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",d);
    
  pItem = (int*) bsearch (&e, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",e);
    
  pItem = (int*) bsearch (&f, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",f);
    
  pItem = (int*) bsearch (&g, keys, 14, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",g);
  return 0;
}

so whenever i hit something that is not in the array i would like to know the closes upper value.

so for 4 closest upper value is 5, then for 8 it is 12 , for 35 it is 44. how would one do this?

can anyone help ???
thank you

baxy

How would you do it. I mean you, as a human being, working with paper and pencil, how would you figure this out? Take the list of numbers you gave: 2, 5, 7, 12, 34, .... How did you figure out that the closes value bigger than 4 is 5? Bigger than 8 is 12? Describe your steps in plain English. Once you do that, converting it to code should be fairly easy.

Most likely, it involved scanning the array, going from smallest to largest. Iterating through an array or list pretty much always means a loop. You have 3 cases to consider as you scan through the array:
1. The current number is smaller than the number in question, what do you do in this case?
2. The current number is equal to the number in question, should you return that number (>=), or are you interested only in numbers that are strictly greater than the number in question. I.e. in the above array, if you were looking for 12, would you select 12 from the array (greater than or equal to), or would you choose 34 (strictly greater than)?
3. The current number is larger than the number in question. Since your array is sorted, this is a fairly easy case to deal with.