/****************************/
/* 二分探索法               */
/*      coded by Y.Suganuma */
/****************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int search(int, int *, int);
int search(char *, char **, int);

int main(int argc, char **argv)
{
	int i1, key_n, res_n, res_c, data_n[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	char *key_c, **data_c;

	data_c = new char * [5];
	for (i1 = 0; i1 < 5; i1++)
		data_c[i1] = new char [6];

	data_c[0] = "eeeee";
	data_c[1] = "ddddd";
	data_c[2] = "ccccc";
	data_c[3] = "bbbbb";
	data_c[4] = "aaaaa";
					// 探索キー
	key_n = atoi(argv[1]);
	key_c = argv[2];
					// 整数の場合
	res_n = search(key_n, data_n, 10);

	if (res_n > 0)
		printf("   %d が見つかりました\n", key_n);
	else
		printf("   %d は見つかりませんでした\n", key_n);
					// 文字列の場合
	res_c = search(key_c, data_c, 5);

	if (res_c > 0)
		printf("   %s が見つかりました\n", key_c);
	else
		printf("   %s は見つかりませんでした\n", key_c);

	return 0;
}

/**************/
/* 整数の場合 */
/**************/
int 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;
}

/****************/
/* 文字列の場合 */
/****************/
int search(char *key, char **data, int n)
{
	int sw = 0, left = 0, right = n - 1, center;

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

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

	return sw;
}