[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [tor-bugs] #7191 [Tor]: smartlist_bsearch_idx() is broken for short lists
#7191: smartlist_bsearch_idx() is broken for short lists
--------------------+-------------------------------------------------------
Reporter: andrea | Owner: andrea
Type: defect | Status: needs_review
Priority: major | Milestone: Tor: 0.2.3.x-final
Component: Tor | Version: Tor: 0.2.4.3-alpha
Keywords: | Parent:
Points: | Actualpoints:
--------------------+-------------------------------------------------------
Comment(by nickm):
Replying to [comment:7 andrea]:
> > Is there some well-documented binary search whose implementation we
now match? It seems silly not to crib from Dijkstra or Knuth or whomever,
given that we already screwed this up once, unless there's a great reason.
>
> Hmm - I didn't look. Possible.
Knuth (AOCP 6.2.1) has, approximately:
{{{
Given a table of records R_1..R_N whose keys are in increasing order K_1 <
K_2 < ... K_N, this algorithm searches for a given argument K.
1. Set lower to 1, upper to N.
2. (invariant: if K is in the table, K_lower <= K <= K_upper.) If upper <
lower, terminate unsuccessfully*. Otherwise let i = floor((lower+upper ) /
2).
3. If K < K_i, goto 4. If K > K_i, goto 5. else K=K_i; terminate
successfully.
4. Set upper = i - 1 and goto 2.
5. Set lower = i + 1 and goto 2.
}}}
So, this one outputs a match, but doesn't trivially output an insertion
point.
Python has a nice simple:
{{{
lo = 0; hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid + 1
else: hi = mid
return lo
}}}
and that one *does* return an insertion point.
--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/7191#comment:11>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs