This question is aboutSearching and Sorting.

(a) Write a functionin Python, Binary Search, which takes as argument a Pythondictionary item_dic, target_item. You should sort thedictionary by its keys into ascending order using the bubblesort algorithm and return a list of values which are correspondingto their keys’ order. And Binary search returns the index ofthe target_item. What is the best & worst-casetime complexity (in terms of Big O-notation) of the searchalgorithm?

• For example, if the given item_dic, target_item: {3:”a”,13:”c”, 5: “b”, -5: “d”}, “b”

After Sorting, the function should return: [“d”, “a”,“b”, “c”]

After Searching, the function should return: 2

Note: You may assumethat the keys in the dictionary are of the same data type, and thevalue for each key in the dictionary is unique. The searchalgorithm is a combination of sorting and searching.

(b) Given thefollowing char_list = [“a”, “f”, “c”, “g”, “d”, “z”], what is theoutput (i.e., printing) at the end of each iteration for theInsertion sort Algorithm?

(a) def binary_search(item_dic, target_item):

#write your answer here

(b)

#write your answer here