探索/二分探索法/二分探索法サンプル - nkym_memo @ ウィキ

二分探索法サンプル

• Node[]を二分探索して、見つかれば表示するプログラム

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

#define NELEM(array) (sizeof(array)/sizeof(array[0]))

struct{
  int key;
  int data;
}Node[20000];

enum{
  RAND_min = 0,
  RAND_max = 1000
};

int Rand(int min,int max)
{
  static int flag;
  if(!flag){
    srand((unsigned int)time(NULL));
    flag = 1;
  }

  return (max - min + 1) * (float)rand()/RAND_MAX + min;
}

void init()
{
  int i;
  for(i = 0;i < NELEM(Node); i++){
    Node[i].key = i;
    Node[i].data = Rand(RAND_min,RAND_max);
    printf("%d %d \n",Node[i].key,Node[i].data);
  }
}

int search(int key)
{
  int low = 0;
  int middle;
  int high = NELEM(Node) - 1;

  while(low <= high){
    middle = (low + high) * 0.5;
    printf("middle : %d\n",middle);
    if(key == Node[middle].key){
      return (Node[middle].data);
    }else if(key < Node[middle].key){
      high = middle - 1;
    }else{
      low = middle + 1;
    }
  }
  return -1;
}

int main(int argc,char *argv[])
{  
  int key = atoi(argv[1]);
  int data;
  init();

  if((data = search(key)) > 0){
    printf("Data found : key %d data %d \n",key,data);
  }else{
    printf("Not found\n");
  }

  return 0;
}

---