二分探索

binary_search.c

#include <stdio.h>
#include <stdlib.h>

int comp(const void *left, const void *right)
{
  return *(int *)left - *(int *)right;
}

int a[10] = {23, 2, 15, 7, 19, 10, 13, 4, 1, 27};

int binary_search(int key)
{
  int ng = -1;
  int ok = (sizeof a) / sizeof(int);

  while (abs(ok - ng) > 1)
  {
    int mid = (ok + ng) / 2;

    if (a[mid] >= key)
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}

int main()
{
  qsort(a, (sizeof a) / sizeof(int), sizeof(int), comp);
  printf("quicksort and binary_search\n");
  for (int i = 0; i < 10; i++) printf("%d ", a[i]);
  printf("\n");
  printf("4 -> %d\n", binary_search(4)); // output: 4 -> 2
  return 0;
}