Ah. I just wrote my first two binary searches in pseudocode. Both of them are semantically incorrect. So it is unlikely that they are right.
So let me write down what I did and explain why they are semantically incorrect. Since my iterative version and recursive version basically derive from the same concept. So I will just use my iterative version as the basis.
In CLRS pseudocode
iterative_binary_search(A,lo,hi,key):
1 while lo != hi
2 mi = floor ( (lo + hi)/2)
3 if A[mi] = key
4 return mi
5 else if A[mi] < key
6 hi = mi
7 else // A[mi] > key
8 lo = mi + 1
I never test it. But I still consider this search to be incorrect. Here is the reason:
At line 5 and 6, hi was set to mi . So in the next iteration the element will be repeatedly considered. Whereas the idea of binary search suggest ones to think a key is in a certain range [l,u]. And after the test at line 3,5,7, there could be three exclusive possibilities.
So does this specific version works though? I have no idea. But I decided to use a version which is semantically correct to start with. So line 6 should be
6 hi = mi - 1
and logically line 1 should be
1 while lo <= hi
This is my self-study page for the book, "Introduction to Algorithm", or commonly known as CLRS. This is also my diary page of how I struggle and grow in the programming world. I hope this blog can help amateurs or professionals, to improve their skills in programming, learning and living. As of Sep 12, 2011, I finished the "exercise read" of Chapter 2 (20110518) and 3 (20110608) and half of Chapter 4.
Shortcut for chapter specific information
Chapter4
(62)
chapter3
(41)
Chapter2
(22)
chapter6
(10)
chapter12
(9)
chapter15
(8)
chapter13
(7)
chapter7
(7)
Chapter10
(5)
chapter5
(5)
Appendix A
(4)
chapter8
(4)
Chapter19
(3)
Chapter22
(3)
Chapter34
(3)
Chapter35
(3)
chapter11
(3)
chapter16
(3)
chapter18
(3)
Appendix C
(2)
Chapter21
(2)
Chapter25
(2)
Chapter26
(2)
Chapter27
(2)
Chapter28
(2)
Chapter29
(2)
Chapter9
(2)
chapter14
(2)
chapter20
(2)
chapter23
(2)
chapter24
(2)
chapter30
(2)
chapter31
(2)
chapter32
(2)
Appendix D
(1)
Chapter1
(1)
Chapter33
(1)
chapter17
(1)
No comments:
Post a Comment