search

stevenhalim / cpbook-code

CP4 Free Source Code Project (C++17, Java11, Python3 and OCaml)
2k stars 493 forks source link

FTree.select throws IndexError: list index out of range #90

Open arsamigullin opened 3 years ago

arsamigullin commented 3 years ago

Hello. Looks like there is a bug in the select function https://github.com/stevenhalim/cpbook-code/blob/fa53432b05cdd30740032b4b4aa401b979949ff4/ch2/ourown/fenwicktree_ds.py#L36

Steps to reproduce:

ft = FTree([1,2,3,4,5])
ft.select(15) # this throws IndexError: list index out of range in line 36

Expected behavior: According to CP4 book, the select function "finds the smallest index/key i so that the cumulative frequency in the range [1..i]>=k". So the function should return 6 because the smallest index (of FTree.ft array) where the cumulative frequency is at least 15 is 6

rchavesf commented 3 years ago

@arsamigullin The answer for your example should be 5. However, the issue exists and it can be solved by https://github.com/stevenhalim/cpbook-code/pull/86.