Algorithm Design and Analysis class problem:

After the great ransomware attack of $2023,$ a company wants to quickly identify which of n files of equivalent size are corrupted. They have a program that will determine if there are any corrupted files in its input.

To improve efficiency, the program can test multiple files in a directory at once. For example, it might combine $10$ files and test them all at the same time. If a test comes back false, that means that none of those $10$ files were corrupted. If the test comes back true, that means that at least one of the files is corrupted, but the program can't identify which one without additional testing.

Assume for simplicity that the program is accurate and runs in constant time no matter how many files are input.

The goal is to minimize the number of times the program is executed. $.$

Design an algorithm that given n files will identify which ones have been corrupted, using no more than O $($k log n$)$ executions, where k is the number of corrupted files. Make sure to justify its correctness an that it uses no more than O$($k log n$)$ tests.

Hint: Construct a Divide$-$and Conquer Algorithm that identifies a single corrupted file executing the program only O$($log n$)$ times. Once you have identified that file, remove that file and repeat until no more corrupted files remain