4 ms·
Range as [a, b) is definitely one of the best ways of thinking about them in the context of most algorithms. b-a is reliably the length; and when you choose a m
by barrkel 17y ago
Range as [a, b) is definitely one of the best ways of thinking about them in the context of most algorithms. b-a is reliably the length; and when you choose a midpoint m, [a, m) and [m, b) don't overlap. Thinking in these terms makes implementing e.g. quicksort and binary search much easier.
- nailer 17y agoMy math is rusty. Could you explain your use of square and regular brackets in [a, m) and [m, b) ?
- alan-crowe 17y agoThe common useage in mathematics is in analysis and topology, to specify subsets of the real numbers. Remembering that open and closed are jargon terms in topology: (a,b) is an open set and contains exactly those x such that a is less than x and x is less than b. [a,b] is a closed set and contains exactly those x such that a is less than or equal to x and x is less than or equal to b For example, one might be thinking about the interval [0,pi] but the function 1/sin x has singularities at both ends of the interval. It is only defined on (0,pi). Notice that 1/x is defined on (0,pi]. It is sometimes convenient to mix up open=exclusive=() and closed=inclusive=[]. These conventions can be carried over into computer science in the obvious way [0,3) = {0,1,2} while (0,3] = {1,2,3} but the motivation is different. In computer science we are more concerned how smoothly our subranges chain together. For example [0,r)+[r,s)+[s,t) = [0,t) while [0,r]+[r+1,s]+[s+1,t] = [0,t]