二分探索

/****************************/
/* 二分探索                 */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include "MT.h"

using namespace std;

/*************************/
/* データの比較（昇順）  */
/*      bsearch 用       */
/*************************/
int compare_n(const void *arg1, const void *arg2)
{
	int *a1 = (int *)arg1;
	int *a2 = (int *)arg2;
	return *a1 - *a2;
}

/**************************************/
/* 二分探索（ Binary Search ）        */
/*      key : 探索するキーデータ      */
/*      data : データ                 */
/*      n : データ数                  */
/*      return : 1 : 見つかった       */
/*               0 : 見つからなかった */
/**************************************/
bool search(int key, int *data, int n)
{
	int sw = 0, left = 0, right = n-1, center;

	if (data[right] > data[left]) {
		while (left < right) {
			center = (left + right) / 2;
			if (data[center] < key)
				left = (center < n-1) ? center + 1 : center;
			else
				right = center;
		}
	}
	else {
		while (left < right) {
			center = (left + right) / 2;
			if (data[center] > key)
				left = (center < n-1) ? center + 1 : center;
			else
				right = center;
		}
	}

	if (data[left] == key)
		sw = 1;

	return sw;
}

#define N 5000000

int main()
{
			// 初期設定
	int s[100000], n = 0;
	int *data = new int [N];
	init_genrand((unsigned)time(NULL));
			// データの設定
	clock_t tm1 = clock();
	for (int i1 = 0; i1 < N; i1++) {
		data[i1] = genrand_int31();
		if (i1%50 == 0 && n < 100000) {
			s[n] = data[i1];
			n++;
		}
	}
	clock_t tm2 = clock();
	printf("保存： %d ms\n", (int)(tm2-tm1));
			// データのソート
	sort(data, data+N);
	clock_t tm3 = clock();
	printf("sort： %d ms\n", (int)(tm3-tm2));
			// データの探索
	for (int i1 = 0; i1 < n; i1++) {
		int sw = search(s[i1], data, N);
		if (sw == 0) {
			printf("***error*** データが見つからない！\n");
			exit(1);
		}
	}
	clock_t tm4 = clock();
	printf("  探索： %d ms\n", (int)(tm4-tm3));
			// データの探索（標準関数 bsearch の利用）
	for (int i1 = 0; i1 < n; i1++) {
		int *sw = (int *)bsearch(&s[i1], data, N, sizeof(int), compare_n);
		if (sw == NULL) {
			printf("***error*** データが見つからない！\n");
			exit(1);
		}
	}
	clock_t tm5 = clock();
	printf("  探索(bsearch)： %d ms\n", (int)(tm5-tm4));
			// データの探索（C++ 標準ライブラリ binary_search の利用）
	for (int i1 = 0; i1 < n; i1++) {
		bool sw = binary_search(data, data+N, s[i1]);
		if (!sw) {
			printf("***error*** データが見つからない！\n");
			exit(1);
		}
	}
	clock_t tm6 = clock();
	printf("  探索(binary_search)： %d ms\n", (int)(tm6-tm5));

	return 0;
}