Attendance

Chris is a teacher teaching a class of approximately $10^{100}$ students. The most annoying thing about teaching this huge number of students is when the school principal asks "Is student with ID $x$ present?" and you have to go through the list of students. Chris figured out 4 methods to make his life easier but he isn't sure which is the best.

1. Sort the list of students according to their IDs. Then binary search for the ID e ach time the principal asks about a student.
2. Sort the list of students according to their IDs. Then look through the list from the beginning each time the principal asks about a student.
3. Leave the list of students as it is. Look through the list from the beginning each time the principal asks about a student.
4. Leave the list of students as it is. Binary search for the ID each time the principal asks the about a student.

Based on the assumption that the school principal doesn't actually care about the students, and he might only asks around $7-8$ questions throughout his entire lifetime, what is the best strategy in general you should suggest Chris?

Details and Assumptions

• Sorting takes $O(n\lg n)$ time.

• Before sorting, the list is not in order.