Answer in Lisp Programing language

Question 1:

Write a recursive function that performs a binary search on a binary tree of sorted numbers represented as a list. For example, the binary tree:

 4 / \ 2 6 / \ / \ 1 3 5 7 

can be represented as: (4 (2 1 3) (6 5 7)). The function should return T (or the number itself) if the number is found, NIL if it is not.

> (defvar n '(17 (5 (2 1 3) (11 7 13)) (31 (23 19 29) (41 37 43)))) n > (binary-search 3 n) T > (binary-search 4 n) NIL > (trace binary-search) (BINARY-SEARCH) > (binary-search 4 n) 0: (BINARY-SEARCH 4 (17 (5 (2 1 3) (11 7 13)) (31 (23 19 29) (41 37 43)))) 1: (BINARY-SEARCH 4 (5 (2 1 3) (11 7 13))) 2: (BINARY-SEARCH 4 (2 1 3)) 3: (BINARY-SEARCH 4 3) 3: returned NIL 2: returned NIL 1: returned NIL 0: returned NIL NIL > (binary-search 43 n) 0: (BINARY-SEARCH 43 (17 (5 (2 1 3) (11 7 13)) (31 (23 19 29) (41 37 43)))) 1: (BINARY-SEARCH 43 (31 (23 19 29) (41 37 43))) 2: (BINARY-SEARCH 43 (41 37 43)) 3: (BINARY-SEARCH 43 43) 3: returned T 2: returned T 1: returned T 0: returned T T

Question 2:

Create a function SUPER-BINARY-SEARCH that is like the BINARY-SEARCH function, but can also be applied to non-numeric data such as symbols or strings. It should take 3 more arguments:

• the function used to compare the order of the items,
• the function used to check if two items are equal, and
• the function used to extract the compared items in the tree from whatever form they are originally in (see examples below).

> (defvar *boy-name-tree* '(Hank (David (Bob Alan Charlie) (Frank Ethan Gerald)) (Luke (Jack Iago Karl) (Neil Mark Oliver)))) BOY-NAME-TREE > (super-binary-search 'John *boy-name-tree* #'string< #'string= #'symbol-name) NIL > (super-binary-search 'Jack *boy-name-tree* #'string< #'string= #'symbol-name) T

> (super-binary-search 43 prime-tree #'< #'= #'identity) T