|
Thank you for your article. I had difficulty understanding the "Binary search implementation" section of the original article for various reasons, despite knowing what binary search is, being familiar with the 2k/2k+1 encoding (from binary heaps), and generally thinking I understood what you're trying to do. I wondered if was the only one struggling with this. Among the difficulties: "restore the index of the resulting element" - it's not clear what this means until after reading the remainder of the section (many times, in my case, due to other difficulties) "We compare it against 4, 2, and 5..." - An error? You compared 'x' against 4, 2, and 3, or b[1], b[2], and b[5], but never against 5 - this would be to the right of 4 and a binary search would not visit it. "..and so we just need to find the number of trailing ones in the binary notation and right-shift by exactly that amount." - You need to shift right that amount plus one. In your example for search(4), after the loop and prior to shifting k=11. In binary this is 1011, which has two trailing ones, but must be shifted right by 3 bits (not 2) to yield k=1 such that b[k] == 4. "eytzinger: 4 2 5 1 6 3 7 8" - it took me surprisingly long to realize this was describing the permutation of values of a[] to indexes of b[] rather than listing the contents of b[] itself with the zero element elided (which coincidentally are the same for the first two elements, despite otherwise not making any sense). Perhaps brevity forces this sort of thing. The presence of 8 in the example's array appears to be an error. At index 8 it would be the left child of 1, which it can't be. Letting n=7 and a={1,2,3,4,5,6,7} agrees with your example, whereas including 8 and setting n=8 rearranges things and forces the root to be 5 rather than 4. |