Hatena::Groupcprogramming

てーげーC言語

2009-02-08

3-1

| 15:48

本にある二分検索

#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>

#define SIZE 1000000

double getrusage_sec()
{
    struct rusage t;
    struct timeval tv; 
    getrusage(RUSAGE_SELF, &t);
    tv = t.ru_utime;
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

int binsearch(int x, int v[], int n); 

int main()
{
  int v[SIZE];
  int i;
  double t1, t2; 

  for(i=0;i<SIZE;i++)
    v[i] = i;

  t1 = getrusage_sec();
  printf("%d\n", binsearch(109, v, SIZE));
  t2 = getrusage_sec();
  printf("time = %10.70f\n", t2 - t1);

  return 0;
}

int binsearch(int x, int v[], int n)  
{
  int low, high, mid;

  low = 0;
  high = n-1;
  while (low <= high) {
    mid = (low+high) / 2;
    if (x < v[mid]) 
      high = mid -1; 
    else if (x > v[mid])
      low = mid + 1;
    else
      return mid;
  }
  return -1;
}
# ./a.out                
109
time = 0.0000280000000000002469136006766348145902156829833984375000000000000000

ループの中でチェックを1回しかしない版

#include <sys/resource.h>
#include <stdio.h>

#define SIZE 1000000

double getrusage_sec()
{
    struct rusage t;
    struct timeval tv; 
    getrusage(RUSAGE_SELF, &t);
    tv = t.ru_utime;
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

int binsearch(int x, int v[], int n); 

int main()
{
  int v[SIZE];
  int i;
  double t1, t2; 

  for(i=0;i<SIZE;i++)
    v[i] = i;

  t1 = getrusage_sec();
  printf("%d\n", binsearch(109, v, SIZE));
  t2 = getrusage_sec();
  printf("time = %10.70f\n", t2 - t1);

  return 0;
}

int binsearch(int x, int v[], int n)  
{
  int low, high, mid;

  low = 0;
  high = n - 1;

  mid = (low+high) / 2;

  while (low <= high && v[mid] != x) {
    mid = (low+high) / 2;
    if (x < v[mid]) 
      high = mid - 1;
    else
      low = mid + 1;
  }

  if (v[mid] == x)
    return mid;

  return -1;
}
# ./a.out                
109
time = 0.0000259999999999999814592754887598857749253511428833007812500000000000

実行時間にはほとんど差はないのでは・・