Question Four (20 Marks) a. Binary Search (BS) uses divide and conquer strategy where problem is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the subproblems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those "atomic" smallest possible sub-problem (fractions) are solved. Given the following nodes in Table Q4a Table Q4a 17 363 6 65 53 29 25 55 31 128 47 42 14 12 3 4 5 6 7 8 9 10 11 12 13 15 14 Perform Binary search for key 42 (show details of search method passes) 1. How many comparison required to search for key 42? ii. What is the complexity of BS, the best and worst case? (7 marks) (1 mark) (2 marks)