Lessons will guide you through each concept using questions.
It is vital to try your best at each question, even if they are difficult. The only way to build understanding and remember things is to actively interact with the concepts, so do not guess answers unless as a last resort.
Read everything that is shown to you and do not skip any text sections. Everything has a purpose and will further your understanding.
Click continue to continue to the next section.
Imagine you are a company manager in 1900. All of your employees have an ID number, which are all stored in a real and physical list and sorted from least to greatest. The first index of that list has the smallest ID number, while the last index has the largest. You have another real and physical list containing names of your employees that is parallel to the ID list. For example, index 1 in the ID list contains the ID for the person whose name is in index 1 of the names list.
Your company has 10,000,000 employees, and you need to find the name of the person corresponding to the ID 404 by finding the index of that ID. Remember, the date is 1900 so you can't just use a computer!
Going through all the IDs one by one would be impossible; it would take at least a few years to do that. You start your task by picking a random ID in the ID list. You draw the ID 256 which is stored at index 9,000,000 (somehow).
How many IDs can you eliminate knowing that ID 256, which is not equal to 404, is stored at index 9,000,000?
Remember, the ID list is sorted!
Since the ID list is sorted from least to greatest, you know that 404 is within the range of indexes 9,000,001 to 10,000,000 inclusive because 404 is greater than 256.
All the numbers stored at the indexes less than 9,000,000 are less than 256 and thus also less than 404. A number that is less than 404 cannot be equal to 404!
How lucky! You just eliminated 9 million possible IDs.
You randomly pick another ID between the indexes 9,000,001 and 10,000,000 inclusive, which you know the ID 404 is within. You get the ID 9999 at the index 9,999,560.
How many IDs can you eliminate this time?
Quite unlucky; you only eliminated 441 IDs.
With these IDs eliminated, you know that 404 is between the indexes 9,000,001 and 9,999,559 inclusive. You stop randomly choosing IDs as the last random draw only eliminated a small number of them.
What index should you draw an ID from to guarantee that you eliminate the largest number of IDs possible?
When you choose an index, you have equal chances of eliminating either the indexes greater than the chosen one or the indexes less than.
Thus, to guarantee that you can always eliminate the most IDs, you should choose the middle most index in range of possible indexes. When you choose the middle index, you're not leaving elimination up to chance: you eliminate the same number of IDs no matter if the ID in the middle index is greater or less than your target ID.
9,499,780 is the middle index in the range 9,000,001 to 9,999,559 inclusive.
You find the ID 2041 at the index 9,499,780, eliminating 499780 IDs with an index greater than 9,499,780.
The range of possible indexes for the ID 404 is now 9,000,001 and 9,499,779.
What is the middle index in this range?
$$9,000,001+\frac{9,499,779-9,000,001}{2}=9,249,890$$
9,249,890 is the middle element.
Repeating the steps of finding the middle index and eliminating half the range of possible IDs, you learn that ID 404 is stored at the index 9,132,401.
Retrieving the name located at index 9,132,401 in the names list, you find that John Doe is the name of the employee with ID 404.
Summary Notes Finish Lesson