Can use help with a discrete Math/Logic problem involving algorithms and compute

Question

Can use help with a discrete Math/Logic problem involving algorithms and computer science:

You have a large text file of people. Each person is represented by one line in the text file. The line starts with their ID number and after that, has the person's name. The lines are sorted by ID number in ascending order. There are n lines in this file. You write a search function that returns the name of a person whose ID number is given The simplest way to do that would be to program a loop that goes through each line and compares the ID number in the line against the given ID number. If there is a match, then it returns the name in that line. This is very inefficient, because the worst-case scenario is that this program needs to go through almost everyone the person we are looking for could be last. using the fact that he tli s sored wil greany speed up the processbus to use a birarysearch alkrhm We go to the middle line of the file first and compare the ID found there (P) to the given ID (Q). (f the number of lines is even, we go above or below the arithmetic middle.) if P=Q then our algorithm terminates . we have found the person we are looking for. If P is less than Q, that means that the person we are looking for is in the second half of the file. We now repeat our algorithm on the second half of the file. If P is greater than Q, that means that the person we are looking for is in the first half of the file. We now repeat our algorithm on the first half of the file. Of what order is the worst-case number of comparison operations that needed for this algorithm to terminate? O log(n)

Explanation / Answer

In this problem, the file is sorted such that the binary search algorithm is used. If the comparison is done such that P is equal to Q, then the algorithm terminates. It means that the algorithm to be searched is found.

If P is less than Q, it means that the element to be searched is in the second half of the file. Repeat the algorithm

If P is greater than Q, it means that the element to be searched is in the first half of the file. Repeat the algorithm

The worst-case number of comparisons that are needed for the algorithm to terminate is log(n)

Explanation: Suppose there are 5 elements and there is the need to find an element, so first pick up the middle element. Compare this middle element with the element to be searched. If the element to be searched is found, terminate. If the element is not found then search in the first half or second half.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.