Think through the issues of BS1 and BS2. Wrote a new iterative version. I verified every steps whether key would be in range [l,u]. This seems to me correct this time.
Also finished Ex. 2.3-5. Need to start to put binary search into my daily practice routine.
Showing posts with label binary search clrs pseudocode. Show all posts
Showing posts with label binary search clrs pseudocode. Show all posts
Tuesday, May 17, 2011
Binary insertion sort 1 (CLRS pseudocode)
Just sketch up a version of binary insertion sort. It is an unstable version but it's quite easy to change it to be stable.
I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).
I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).
Binary insertion sort 1 (CLRS pseudocode)
Just sketch up a version of binary insertion sort. It is an unstable version but it's quite easy to change it to be stable.
I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).
I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).
Wednesday, May 11, 2011
Binary Search 1 and 2 (CLRS pseudocode)
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
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
Subscribe to:
Posts (Atom)