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.