c++ ocument/d/1cuk0louuS-Gqbal8MgX-znWzblacw Xbct4azy5f6Mi/edit ointers Binary S

Question

c++

ocument/d/1cuk0louuS-Gqbal8MgX-znWzblacw Xbct4azy5f6Mi/edit ointers Binary Search Divide and Conquer Task 2 Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number if you are given the hint 'higher or lower' for each guess you make? This may be considered a trick question, since it's deceptively easy. Read the question carefully and you'll note that the question asks for the 'minimum number of guesses. Think about it -someone can guess the right question on their first try right? So, the answer here would be 1, since it would take only one correct guess to find a specific number. Finding the maximum number of guesses But, what if we wanted to find the maximum number of guesses? cancer-2017.34 (1) exe ^ -get setup ( ^ exe CL

Explanation / Answer

Basic binary search is we find the number at middle at each step.

So let’s say we have number in range (x,y) then our guess could be found at (x+y)/2 and in case that’s you find it at very first step then we got our minimum number of guess which is 1.

Now if we need to find maximum number of guesses we need to see whether our guess is higher than the number or lower. If higher then our new interval will become [((x+y)/2)+1,y] and if lower then it will become [x,((x+y)/2)-1]. And we keep on continuing the same process until the interval collapse.

Now keeping the above in mind let’s see for our range. Our interval is [1,1000] so first guess will be 500. Then we get the hint “higher” so the interval becomes [501,1000] and keeping the formula in mind next guess becomes 750. And if we for hint lower then interval becomes [1,499] and the guess becomes 250.Now as we want to mind maximum guesses we need to consider the worst case and it is log2n is the complexity for binary search worst case. We have n = 1000 so our maximum number of guess becomes log21000 which is 9.96 so approximately 10.

Basic binary search is we find the number at middle at each step.

So let’s say we have number in range (x,y) then our guess could be found at (x+y)/2 and in case that’s you find it at very first step then we got our minimum number of guess which is 1.

Now if we need to find maximum number of guesses we need to see whether our guess is higher than the number or lower. If higher then our new interval will become [((x+y)/2)+1,y] and if lower then it will become [x,((x+y)/2)-1]. And we keep on continuing the same process until the interval collapse.

Now keeping the above in mind let’s see for our range. Our interval is [1,1000] so first guess will be 500. Then we get the hint “higher” so the interval becomes [501,1000] and keeping the formula in mind next guess becomes 750. And if we for hint lower then interval becomes [1,499] and the guess becomes 250.Now as we want to mind maximum guesses we need to consider the worst case and it is log2n is the complexity for binary search worst case. We have n = 1000 so our maximum number of guess becomes log21000 which is 9.96 so approximately 10.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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