[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