int BinarySearch(int arr[], int low, int high, int key)
{
     int mid; // = (low + high)/2;
     int  done = 0;
     
     if (high < low) 
           return -1;
       
     mid = (low + high)/2;
         
     while (!done)
     {
         if(key==arr[mid])
             return mid;
         else if (key > arr[mid])
             mid = ((mid+1) + high) / 2;
         else if (key < arr[mid])
            mid = (low + (mid-1)) / 2;
     }
     
     return -1;
}

 else if (key > arr[mid] && key <  arr[mid+1])

 
   while (first < last) {
        size_t mid = first + (last - first) / 2;

        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == x) {
        /* Искомый элемент найден. last - искомый индекс */
        return FOUND(last);
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
        return NOTFOUND(last);
    }

int BinarySearch(int a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0] > key) 
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1] < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last] == key)
    {
        *found = 1;
        return last;
    }
    else
    {
        *found = 0;
        return last;
    }
}

int BinarySearch(int a[], int pos, int key, int *found)

int BinarySearch(int a[], int pos, int key, int *result)

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

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

#define MESSAGE_SIZE 20
#define MESSAGE_ARR_SIZE  20

typedef struct TEST_MESSAGE_S
{
    int id;
    char data[MESSAGE_SIZE];
}TEST_MESSAGE;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE];

char spectra_packet[20];

int  spectra_id;
int spectra_command;

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found);
void InsertElement(int id, char *msg);
void DeleteElement(int id);

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0].id > key) 
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1].id < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid].id)
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last].id == key)
    {
        *found = 1;
        return last;
    }
    else
    {
       *found = 0;
        return last;
    }
}

void UpdateElement(int id[, char msg[])
{
}

void InsertElement(int id, char *msg)
{
    int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*(glob_pos-idx));   //glob_pos-1-idx
        
        messages[idx].id = id;
        memcpy(messages[idx].data, msg, sizeof(spectra_packet));
        
       //if (glob_pos < MESSAGE_ARR_SIZE)
        glob_pos++;
    }
}

void DeleteElement(int id)
{
     int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found) 
    {
       memmove(messages+idx, messages+(idx+1), sizeof(TEST_MESSAGE)*glob_pos-1-idx);
       
       if (glob_pos > 0)
           glob_pos--;
    }
}

 /////////////////////////////TEST  AREA ///////////////////////////////////
  for (idx = 0; idx < 20; idx++)
  {
      messages[idx].id = -1;
  }
  
  while(1)
  {
      spectra_id = spectra_packet[0];
      spectra_command = spectra_packet[1];
      
      switch (spectra_command)
      {
            case 1:
                if (glob_pos < MESSAGE_ARR_SIZE)
                    InsertElement(spectra_id, spectra_packet);
            break;
            case 2:
                DeleteElement(spectra_id);
            break;
      }
  }
/////////////////////////////////////////////////////////////////////