This exercise is part of my open university homework.
Presented with a brief introduction to the workings of binary search and five code snippets using Pascal, I had to figure out which of these fragments are correct implementations of the given search algorithm.
Binary Search - You're doing it wrong...
Based on the description and after a quick visit to Youtube, I came up with the following idea on how binary search works:
I created a sorted list in ascending order containing 10 random elements: 1, 34, 45, 50, 51, 60, 71, 75, 84 and 99. My search value was 84.
I determined the lists middle element (<list size> div 2) which is 5, and compared its value (50) with my search value. As 84 is greater than 50, I discarded all elements in the lists lower half including 50.
Based on the remaining lists upper half (60, 71, 75, 84 and 99) I kept repeating this halving process until the lists middle element matched the search value.
It took four iterations to find the value 84.
I was fine with my understanding of the algorithm until I ran the first sample implementation using my above list and search value as inputs. Instead of four iterations the program completed the search process taking only three iterations.
This is the given code snippets which...
...I embedded in a little program frame...
...and added some output...
I was stuck for a while until I realized my faulty assumption: Making the list smaller and smaller each iteration.
Implementing this "algorithm", I would either have to remove the discarded elements form the list or copy the remaining elements into a new list.
As my exercise did not mention neither option, this meant back to the drawing board.
Binary Search - You're doing it right...
This image shows the workings of the code snippet:
The field size remains of constant length 10.
The first element is (upperBound + lowerBound) div 2, (10 + 1) div 2 = 5.
As the search value is neither located at position 1 to 5, the implementation increases the value of loverBound by 1, 5 + 1 = 6. Again it calculates (upperBound + lowerBound) div 2, (10 + 6) div 2 = 8.
The value of the eighth element is 75. As the search element is neither located at position 1 to 8, again the value of lowerBound is incremented by 1, 8 + 1 = 9. (10 + 9) div 2 = 9. The value of the ninth list element is 84, which matches our search value. This makes 3 iterations total.
Having a better understanding of how binary search works, I had a look at the other code snippets.
To determine wether the sample code is a valid implementation of binary search, I have to check if
- searching is performed according to the given algorithm
- it terminates properly in case the list contains the search value
- it terminates properly in case the list does not contain the search value
- it works properly on a list with length n
- it works properly on a list with length n + 1
The good, the bad....
As this post already became rather lengthy, I will limit myself to one good and one bad example.
Let's see how the first code snippet (shown above) overall performs:
|
Match |
No match |
| length n |
x |
x |
| length n + 1 |
x |
x |
This makes it a proper implementation of the binary search algorithm.
The second sample...
...produces the following results embedded in my little program frame:
| Match | No match |
| length n | x | - |
| length n + 1 | x | - |
In case the list contains the search value, it's found.
But in case the list does not contain the search value, the program does not even terminate.
What's wrong here?
Let's take my list of ten elements (1, 34, 45, 50, 51, 60, 71, 75, 84 and 99) and a search value which is not part of the list, 86.
The first step calculates the lists middle, (0 + 10) div 2 = 5, and compares 86 with the value of the fifth list element, which is 51. So far so good.
Now as the search value is greater than the 51, the value of lowerBound is set to the value of middle, 5. The value of found is false.
The next iteration again calculates the middle (10 + 5) div 2 = 7 and compares 86 with 71. The value of lowerBound becomes 7, and the loop body gets executed another time.
(10 + 7) div 2 = 8. 86 > 75? Yes. lowerBound 8.
(10 + 8) div 2 = 9. 86 > 84? Yes, lowerBound 9.
(10 + 9) div 2 = 9. 86 > 84? Yes, lowerBound 9.
(10 + 9) div 2 = 9. 86 > 84? Yes...................
(10 + 9) div 2 = 9. 86 > ..........................
(10 + 9) div 2 =...............................
................................................
........................................
..............................
.......................
..................
............
........
....
..
.
