Programming: Data Structures
COS2611
Assignment 3 - 2022
, Question 1: Searching
Describe how the binary search algorithm searches for 27 in the following list:
5, 6, 8, 12, 15, 21, 25, 31.
Solution:
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
Binary search algorithm searches for elements in a sorted list. It compares the search
element with the middle element in the list, if the search element is equal to the middle
element, the position of this element is returned. Otherwise, the lower left or the upper
right of the middle element is searched.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 0 Mid=3 last=7
In the above list, 27 is compared to 12. Surely, 27 should be on the upper right of the list.
The new search list is shaded below.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 4 Mid= 5 last=7
Again, compare 27 with 21. 27 must be on upper right.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 6
Mid= 6 last=7
27 should be on the right of 25.
2
COS2611
Assignment 3 - 2022
, Question 1: Searching
Describe how the binary search algorithm searches for 27 in the following list:
5, 6, 8, 12, 15, 21, 25, 31.
Solution:
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
Binary search algorithm searches for elements in a sorted list. It compares the search
element with the middle element in the list, if the search element is equal to the middle
element, the position of this element is returned. Otherwise, the lower left or the upper
right of the middle element is searched.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 0 Mid=3 last=7
In the above list, 27 is compared to 12. Surely, 27 should be on the upper right of the list.
The new search list is shaded below.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 4 Mid= 5 last=7
Again, compare 27 with 21. 27 must be on upper right.
Position 0 1 2 3 4 5 6 7
Values 5 6 8 12 15 21 25 31
First = 6
Mid= 6 last=7
27 should be on the right of 25.
2
