#include <bits/stdc++.h>

using namespace std;

struct HocSinh {
	string tenHS;
	string hoDem;
	int namSinh;
	string diaChi;
};

int Swap(HocSinh &a, HocSinh &b) {
	HocSinh tmp = a;
	a = b;
	b = tmp;
}

int Quick_Sort(HocSinh a[], int left, int right) {
	string pivot = a[(left + right) / 2].tenHS;
	int i = left;
	int j = right;
	while (i < j) {
		while (a[i].tenHS < pivot) {
			i++;
		}
		while (a[j].tenHS > pivot) {
			j--;
		}
		if (i <= j) {
			Swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (i < right) {
		Quick_Sort(a, i, right);
	}
	if (left < j) {
		Quick_Sort(a, left, j);
	}
}

void hienThi(HocSinh hs[], int n) {
	Quick_Sort(hs, 0, 5);
	for (int i = 0; i < n; i++) {
		cout << hs[i].hoDem << " " << hs[i].tenHS << "\t" << hs[i].namSinh << "\t" << hs[i].diaChi << endl;
	}
}

int timKiem(HocSinh hs[], int l, int r, string tenHS) {
	if (l == r) {
		if (hs[l].tenHS == tenHS)  return l;
		else return -1;
	} else {
		int m = (l + r) / 2;
		int kq1 = timKiem(hs, l, m, tenHS);
		int kq2 = timKiem(hs, m + 1, r, tenHS);
		if (kq1 >= l && kq1 <= r) return kq1;
		if (kq2 >= l && kq2 <= r) return kq2;
	}
}

int main() {
	HocSinh hs[] = {
		{"Vu", "Luu Van", 1995, "Uy No"},
		{"Anh", "Nguyen Tuan", 1995, "Kinh No"},
		{"Hoang", "Vuong Tan", 1995, "Uy No"},
		{"Hoang", "Le Huy", 1995, "Kim Chung"},
		{"Binh", "Tran Minh", 1995, "Uy No"},
		{"Minh", "Le The", 1995, "Kim Chung"}
	};
	string tenHS;
	hienThi(hs, 6);
	cout << "Nhap ten hoc sinh can tim: ";
	cin >> tenHS;
	int pos = timKiem(hs, 0, 5, tenHS);
	cout << "Ket qua tim kiem: " << endl;
	if (pos != -1) {
		cout << hs[pos].hoDem << " " << hs[pos].tenHS << "\t" << hs[pos].namSinh << "\t" << hs[pos].diaChi << endl;
	} else {
		cout << "Khong tim thay";
	}
	return 0;
}