Part $1$: Implementing Binary Search

In the template, a function called $`$binarySearch$()`$ is provided with a partial

implementation. Your task is to complete this function to allow searching for Monster IDs in

a sorted list. The binary search should operate by repeatedly dividing the search interval in

half until the target Monster ID is found or the interval is empty.

Instructions:

$-$ Locate the $`$FIXME$`$ comment inside the $`$binarySearch$()`$ function.

$-$ Implement the loop that adjusts $`$left$`$ and $`$right$`$ pointers based on the middle element.

$-$ Test your implementation using the sample Monster IDs provided in $`$main$()`.$

Part $2$: Constant Time Retrieval

You need to complete the $`$getMonsterCount$()`$ function that retrieves the count of a specific

monster type. This function will use an $`$unordered$\_$map$`$ to efficiently retrieve the count in

constant time.

Instructions:

$-$ Locate the $`$FIXME$`$ in $`$getMonsterCount$()`.$

$-$ Use the hash map $(`$unordered$\_$map$`)$ to check if a monster type exists and return its count.

$-$ If the type does not exist, return $`0`.$

Part $3$: Recursive Family Tree

A family tree is represented using the $`$MonsterNode$`$ structure. Your task is to implement

the $`$countGenerations$()`$ function to determine the number of generations in a monster

family tree. This function must be implemented recursively.

Instructions:

$-$ Locate the $`$FIXME$`$ in $`$countGenerations$()`.$

$-$ Implement the base case: if the node is $`$nullptr$`,$ return $`0`.$

$-$ Recursively determine the maximum depth of descendants and return the number of

generations.

$-$ Add descendants using $`$addDescendant$()`$ as needed in $`$main$()`.$

Part $4$: Census Report Generation

You need to complete the $`$generateCensusReport$()`$ function to display details about

Algorithmtown's monster population. This function should include information like the

total population, the distribution of monster types, and the median Monster ID$.$

Instructions:

$-$ Locate the $`$FIXME$`$ comments in $`$generateCensusReport$()`.$

$-$ Iterate through the $`$monsterTypeCounts$`$ hash map to display the count of each monster

type.

$-$ Implement logic to calculate and display the median Monster ID$.$

Memory Management and Cleanup

In this project, you are dynamically allocating memory for the family tree nodes. To avoid

memory leaks, it's important to delete these nodes once they are no longer needed.

Instructions:

$-$ Properly delete the dynamically allocated nodes in $`$main$()`.$

$-$ This task is optional but strongly recommended to help you understand memory

management in C$++.$

General Tips:

$-**$Take It Step by Step$**$: Start by implementing one part of the project at a time, testing it

thoroughly before moving on$.$

$-**$Test Early and Often$**$: Regular testing will help you catch and fix issues before they

become larger problems.

$-**$Use Meaningful Variable Names$**$: Keep your code readable by using clear and

descriptive variable names.

$-**$Ask Questions$**$: If you get stuck, don't hesitate to ask questions or collaborate with

peers $($without copying!$)$