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

#define MAX_DATABASE_SIZE 100
#define MAX_STR_LEN 30


void getstr(char s[]) {
	char c;
	int i = 0;
	while((c = getchar()) != '\n')
		s[i++] = c;
	s[i] = '\0';
}

bool binSearch(char s[], char **database, int databaseSize) {
	int l = 0, r = databaseSize, m;
	int cmp;
	while (l < r) {
		m = l + (r - l) / 2;
		cmp = strcmp(s, database[m]);
		if (cmp <= 0)
			r = m;
		else
			l = m + 1;
	}

	return (r < databaseSize && strcmp(s, database[r]) == 0);
}

int main() {
	FILE *file = fopen("database.txt", "r");

	int i = 0, j = 0, databaseSize = 0;
	char c;
	char **database = (char **)malloc(MAX_DATABASE_SIZE * sizeof(char *));
	bool finish = false;
	
	for (i = 0; i < MAX_DATABASE_SIZE && !finish; i++) {
		database[i] = (char *)malloc(MAX_STR_LEN * sizeof(char));
		
		j = 0;
		while ((c = fgetc(file)) != '\n' && c != EOF)
			database[i][j++] = c;
		
		finish = (j == 0);
	}
	databaseSize = i - 1;
	fclose(file);

	char s[MAX_STR_LEN];
	getstr(s);
	if (binSearch(s, database, databaseSize))
		printf("Found!");
	else
		printf("Not found!");


	for (i = 0; i < databaseSize; i++)
		free(database[i]);
	free(database);

	return 0;
}