Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

The aswers that you have may not be correct Question 2 Implement a binary search typing program. Repeatedly ask the user what range of letters

The aswers that you have may not be correct

Question 2 Implement a binary search typing program. Repeatedly ask the user what range of letters their letter is in until you get the right one. Stop when the user types the exclamation point. Submit the code in the file main.c. You may supply additional files if you wish to. You main program must be in main.c. Assumption: You may assume that the user will only type: y, Y, n, or N. The user will only enter exactly 1 character and will not enter any other characters. You do not have to provide any error checking on this input. Remember we are simulating a person who can only give us yes/no answers. Assumption: You may assume the user will never type more than 100 characters before entering '!'. Example Execution Trace: Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) n Is your letter between 'b' and 'c'? (y/n) y Is your letter between 'b' and 'b'? (y/n) n Is your letter 'c'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) n Is your letter between '.' and '.'? (y/n) n Is your letter 'a'? (y/n) y Is your letter between ' ' and 'l'? (y/n) n Is your letter between 'm' and 's'? (y/n) n Is your letter between 't' and 'w'? (y/n) y Is your letter between 't' and 'u'? (y/n) y Is your letter between 't' and 't'? (y/n) y Is your letter 't'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) y Is your letter between ' ' and ' '? (y/n) n Is your letter '!'? (y/n) y You typed: cat Binary Search has an optimization you must take advantage of here. Sometimes there is no point in asking one of the questions. Take the following example: ./main Is your letter between ' ' and 'l'? (y/n) n Is your letter between 'm' and 's'? (y/n) y Is your letter between 'm' and 'p'? (y/n) n Is your letter between 'q' and 'r'? (y/n) n Is your letter 's'? (y/n) y Is your letter between ' ' and 'l'? (y/n) y Is your letter between ' ' and 'e'? (y/n) y Is your letter between ' ' and 'a'? (y/n) y Is your letter between ' ' and '!'? (y/n) y Is your letter between ' ' and ' '? (y/n) n Is your letter '!'? (y/n) y You typed: s When we type s, there is no need to ask Is your letter between 's' and 's'? (y/n) but for space there is a need to ask Is your letter between ' ' and ' '? (y/n) Let's look at why: Alphabet: " !.abcdefghijklmnopqrstuvwxyz" Question: Is your letter between ' ' and 'l'? (y/n) Answer: n Alphabet: "mnopqrstuvwxyz" Question: Is your letter between 'm' and 's'? (y/n) Answer: y Alphabet: "mnopqrs" Question: Is your letter between 'm' and 'p'? (y/n) Answer: n Alphabet: "qrs" Question: Is your letter between 'q' and 'r'? (y/n) Answer: n Alphabet: "s" Question: Is your letter 's'? (y/n) Answer: n The number of letters in the set was ODD. That means the options had to be 's. We can skip one question. That will not be the case in the next example. Alphabet: " !.abcdefghijklmnopqrstuvwxyz" Question: Is your letter between ' ' and 'l'? (y/n) Answer: y Alphabet: " !.abcdefghijkl" Question: Is your letter between ' ' and 'e'? (y/n) Answer: y Alphabet: " !.abcde" Question: Is your letter between ' ' and 'a'? (y/n) Answer: y Alphabet: " !.a" Question: Is your letter between ' ' and '!'? (y/n) Answer: y Alphabet: " !" Question: Is your letter between ' ' and ' '? (y/n) Answer: n Alphabet: "!" Question: Is your letter '!'? (y/n) Answer: y This time, the range was even " !.a". That means when we cut it down we don't know if you want the space or the exclamation point. We cannot save ourselves the extra question here.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

SQL Instant Reference

Authors: Gruber, Martin Gruber

2nd Edition

0782125395, 9780782125399

More Books

Students also viewed these Databases questions

Question

Advance warning and an explanation for the layoff.

Answered: 1 week ago