落書きノート

ふと自分が気になった事を書いてます

C言語で不定期練習 二分探索法 バイナリサーチ

// 演習問題3-8

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

int int_cmpr(const int *a, const int *b) {
  return *a == *b;
}

void *binsearch(const void *key, const void *base, size_t nmemb,
                size_t size, int (*compar)(const void *, const void *)) {
  int pl = 0;
  int pr = nmemb - 1;
  int pc;

  do {
    pc = (pl + pr) / 2;
    if(compar(base + pc * size, key))
      return (void *)base + pc * size;
    else if(*(int *)base + pc * size > *(int *)key)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while (pl <= pr);

  return NULL;
}

int main(void) {
  int i, nx, ky;
  int *x, *p;

  puts("bsearch関数による探索");
  printf("要素数 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("降順に入力してください。\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  
  for(i = 1; i < nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while (x[i] > x[i - 1]);
  }
  
  printf("探す値 : ");
  scanf("%d", &ky);
  
  p = binsearch(&ky,
                x,
                nx,
                sizeof(int),
                (int (*)(const void *, const void *))int_cmpr
                );
  
  if(p == NULL)
    puts("探索に失敗しました。");
  else
    printf("%dはx[%d]にあります。\n", ky, (int)(p - x));
  free(x);
  
  return 0;
}

新・明解C言語によるアルゴリズムとデータ構造

新・明解C言語によるアルゴリズムとデータ構造