Reference no: EM133059352

Learning Activity: Flowchart and Pseudocode exercise - binary search

In one of the essential resources, we asked you to draw a flowchart and write up some pseudocode for searching for a particular element in an arbitrary list. Now we will look at a more sophisticated algorithm and ask you to draw a flowchart and pseudocode for it.

Suppose again you have a list of n elements a_list and a target value key. You would like to find out whether key is contained in the a_list. In this learning activity, however, the list a_list is sorted in an increasing order, that means a_list[0] <= a_list[1] <= a_list[2] .... Do you want to amend the flowchart and pseudocode you did earlier so that you can use as less comparison as possible to ascertain whether the target value key is contained in a_list.

If you know that all the elements in a_list are sorted increasingly, it would not be wise to compare each element in a_list with key and to see whether they would match or not. You would instead first compare the element right in the middle of a_list. If that element is larger than key, then you do not need to compare any elements on the right-hand side of the middle element in a_list because all of them will be larger than key. On the contrary, if that middle element is smaller than key, then you do not need to compare the left half. This process is repeated until you find key in a_list, or you exhausted all the elements in a_list. This idea is illustrated in the figure below.

Now draw a flowchart and write up pseudocode for this algorithm and post them on Module 2.2 Flowchart and Pseudocode discussion forum.