/* Returns the smallest |i| such that |array[i] == key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n int|s. */
int
seq_search (int array[], int n, int key)
{
  int i;

  for (i = 0; i < n; i++)
    if (array[i] == key)
      return i;
  return -1;
}

/* Returns the smallest |i| such that |array[i] == key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an modifiable array of |n int|s
   with room for a |(n + 1)|th element. */
int
seq_sentinel_search (int array[], int n, int key)
{
  int *p;

  array[n] = key;
  for (p = array; *p != key; p++)
    /* Nothing to do. */;
  return p - array < n ? p - array : -1;
}

/* Returns the smallest |i| such that |array[i] == key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n| |int|s sorted in ascending order. */
int
seq_sorted_search (int array[], int n, int key)
{
  int i;

  for (i = 0; i < n; i++)
    if (key <= array[i])
      return key == array[i] ? i : -1;

  return -1;
}

/* Returns the smallest |i| such that |array[i] == key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an modifiable array of |n int|s,
   sorted in ascending order,
   with room for a |(n + 1)|th element at the end. */
int
seq_sorted_sentinel_search (int array[], int n, int key)
{
  int *p;

  array[n] = key;
  for (p = array; *p < key; p++)
    /* Nothing to do. */;
  return p - array < n && *p == key ? p - array : -1;
}

/* Returns the smallest |i| such that |array[i] == key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n int|s,
   sorted in ascending order,
   with room for an |(n + 1)|th element to set to |INT_MAX|. */
int
seq_sorted_sentinel_search_2 (int array[], int n, int key)
{
  int *p;

  array[n] = INT_MAX;
  for (p = array; *p < key; p++)
    /* Nothing to do. */;
  return p - array < n && *p == key ? p - array : -1;
}

/* Returns the offset within |array[]| of an element equal to |key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n| |int|s sorted in ascending order. */
int
binary_search (int array[], int n, int key)
{
  int min = 0;
  int max = n - 1;

  while (max >= min)
    {
      int i = (min + max) / 2;
      if (key < array[i])
        max = i - 1;
      else if (key > array[i])
        min = i + 1;
      else
        return i;
    }

  return -1;
}

/* Returns the offset within |array[]| of an element equal to |key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n| |int|s sorted in ascending order,
   with |array[-1]| modifiable. */
int
uniform_binary_search (int array[], int n, int key)
{
  int i = (n + 1) / 2 - 1;
  int m = n / 2;

  array[-1] = INT_MIN;
  for (;;)
    {
      if (key < array[i])
        {
          if (m == 0)
            return -1;
          i -= (m + 1) / 2;
          m /= 2;
        }
      else if (key > array[i])
        {
          if (m == 0)
            return -1;
          i += (m + 1) / 2;
          m /= 2;
        }
      else
        return i >= 0 ? i : -1;
    }
}

/* Plug-compatible with standard C library |bsearch()|. */
static void *
blp_bsearch (const void *key, const void *array, size_t count,
             size_t size, int (*compare) (const void *, const void *))
{
  int min = 0;
  int max = count;

  while (max >= min)
    {
      int i = (min + max) / 2;
      void *item = ((char *) array) + size * i;
      int cmp = compare (key, item);

      if (cmp < 0)
        max = i - 1;
      else if (cmp > 0)
        min = i + 1;
      else
        return item;
    }

  return NULL;
}

/* Compares the |int|s pointed to by |pa| and |pb| and returns positive
   if |*pa > *pb|, negative if |*pa < *pb|, or zero if |*pa == *pb|. */
static int
compare_ints (const void *pa, const void *pb)
{
  const int *a = pa;
  const int *b = pb;

  if (*a > *b)
    return 1;
  else if (*a < *b)
    return -1;
  else
    return 0;
}

/* Returns the offset within |array[]| of an element equal to |key|,
   or |-1| if |key| is not in |array[]|.
   |array[]| must be an array of |n| |int|s sorted in ascending order. */
static int
binary_search_bsearch (int array[], int n, int key)
{
  int *p = blp_bsearch (&key, array, n, sizeof *array, compare_ints);
  return p != NULL ? p - array : -1;
}

/* Cheating search function that knows that |array[i] == i|.
   |n| must be the array size and |key| the item to search for.
   |array[]| is not used.
   Returns the index in |array[]| where |key| is found,
   or |-1| if |key| is not in |array[]|. */
int
cheat_search (int array[], int n, int key)
{
  return key >= 0 && key < n ? key : -1;
}