Answer Happy

3) Let us play a game. While playing this game you will be able to appreciate how two different solutions to the same problem can vary so much in term s of efficiency. The game is that the computer will randomly select an integ er from 1 to N and ask you to guess it. [Hint]: To help you guess the number correctly, the computer will tell you if each guess is too high or too low. The good thing is that there is no limit on number of guesses. You can make as many guess as you want to guess th at number. There are two ways to succeed in this game. First is the linear s earch and second is the binary search In linear search, you will guess the number as 1, then 2, then 3, then 4, and so on, until you guessed the right number. So you are guessing all the numbers as if they were lined up in a row. This technique is fine but just wo nder how many guesses you would have to make. If the computer selects N, you would need N guesses. If N is 1 then, of course, you will make it in th e very first guess itself. Even if Nis a small number like 5 or 10, then it is sti Il fine but just imagine what will be the number of guesses if N is a large nu mber Now let us explore the binary search technique. Since the computer tell s you whether a guess is too low, too high, or correct, it is better to start by guessing N/2. If the number selected by the computer is less than N/2, the n using the computer's information that the guess is too high, you can elimi nate all the numbers from N/2 to Nin just one go. If the number selected b y the computer is greater than N/2, then all elements from 1 through N/2 ar e eliminated right away. So with one guess you have narrowed down your p ossible guesses by half. Isn't that interesting and an intelligent move? Keep on cutting down the set of possible numbers by half with every guess that you make. The following table shows the maximum number of Max Binary Search Guesses Max Linear Search Guesses 10 4 7 100 VALUE OF N 10 100 1,000 10,000 100,000 1,000,000 10 14 1.000 10,000 100.000 1,000,000 17 20 guesses for linear search and binary search for a few number sizes: Required: Write the pseudocode and draw the flowchart for the above pro blem statement.