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

/*--- 要素数nの配列aからkeyと一致する要素を線形探索（番兵法）---*/
int search(int a[], int n, int key)
{
	int i = 0;

	a[n] = key;			/* 番兵を追加 */

	while (1) {
		if (a[i] == key)
			break;		/* 見つけた */
		i++;
	}

	return i == n ? -1 : i;
}

int bin_search(const int a[], int n, int key)
{
	int pl = 0;			/* 探索範囲先頭の添字 */
	int pr = n - 1;		/* 　 〃 　末尾の添字 */
	int pc;				/* 　 〃 　中央の添字 */

	do {
		pc = (pl + pr) / 2;
		if (a[pc] == key)		/* 探索成功 */
			return pc;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			pr = pc - 1;
	} while (pl <= pr);

	return -1;					/* 探索失敗 */
}

int is_sorted(const int a[], int n){
}

int main(void){
	int i, nx;
	int *x;
	int c1, c2;

	printf("要素数:");
	scanf_s("%d", &nx);
	printf("1から%dまでの要素をもつ配列を生成します.\n", nx);
	x = calloc(nx, sizeof(int));
	for (i = 0; i < nx; i++){
		x[i] = i + 1;
	}

	c1 = search(x, nx, 0);
	c2 = bin_search(x, nx, 0);
	puts("最大探索回数(探索失敗までの実行回数)は:");
	printf("線形探索(番兵法) : \t%d回\n", c1);
	printf("2分探索 : \t\t%d回\n", c2);

	free(x);
	return 0;
}