correctness is somewhat in the eye of the beholder. If in a
particular application it is known that the array is not empty,
or that the sought-for element is present, then you can write
slightly simpler code that would fail some of the stress testing
that a more general code needs.
My code worked i all such cases. But there were two assumptions,
based on the technology I was using, that would make my code less
than theoretically universal, so you have a good point not with
those specifics above but with that general idea and the specifics
you cite later.
People in those days got jobs done, they weren't concerned with
formal correctness according to some abstract spec.
Well, if my subroutine was supposed to handle a particular class of
problems, I tried to make sure it really would handle them all. It
was easier for me to write a mathematially "pure" spec and then
satisfy it, instead of write an ugly special-cases spec and
constantly check if the exceptions in the spec match the failure
modes of the program. (In case you haven't guessed, I was a math
major. I liked science better in elementary school, but did better
in math, so I was directed toward math instead of science, although
I treat math research from a scientific viewpoint instead of a
find-a-formal-proof purist viewpoint. Find-a-proof is just to show
everyone I got the correct solution.)
You're talking about a period that was about a decade before the
first undergraduate CS courses, and long before anyone but the
odd fanatic worried about "correctness", as opposed to "working".
I was in that period. When I was undergraduate in math department
(at SCU), the only programming courses available were FORTRAN (only
for the graduate school EE program) and 1401 AutoCoder (only for
MBA program). I was allowed to browse the FORTRAN and machine
language manuals in the machine room, and use the computer while
the EE people were in there so a supervisor was present so long as
I always let the EE people have priority on the machine (IBM 1620).
Later they learned to trust me, so I was allowed to stay in the
machine room after everyone had left, and I often stayed all night
until people started showing up the next morning to claim their
priority on the machine.
I heard rumors that some other university had programming courses
for undergraduates, but I couldn't afford to go there, and I got by
just fine reading the manuals and figuring out things by
experience. The most "useful" program I wrote on my own was to
perform abstract differentiation on polynomials, which involved
computing coefficients and variable-powers of the individual terms
using the product rule then collecting similar terms. Later I got
my first paying software jobs writing payroll program (to replace
IBM 407 plugboard program) and pre-registration (brand new
automation never before done there).
As for formal CS (S for "science", not "programming") courses, I
didn't even hear of such until many years later.
You learned programming by attending a two-day course on the
Autocode of a particular computer, ...
Back then I never even heard of such. Maybe the EE "course" in
Fortran programming was actually like that, two days of lecture
then nothing but lab after that, I wouldn't know the details.
Nowadays, that particular algorithm is one of the common early
tasks in an algorithms module. You tell the class what you want
their code to do, and give them a few minutes to write it.
Do you (not you personally, the instructor of said class) simply
tell them the data is already sorted into correct sequence, in an
array, and you want an efficient way to find the matching element
if it's present? Or do you also mention "divide the array in half"
as a clue how to do it?
When you say a few minutes to write it, do they have an actual
machine to try it on, or do they have to do it all without machine?
Then you find out whether their code works if the array is empty,
if there is only one element, if the target is larger/smaller
than the last/first element, and so on. It doesn't, so that
gives you the chance to talk about invariants, pre- and
post-conditions, program structure in general, blah-de-blah,
That sounds like an interesting way to run such a class. I've never
seen that teaching method used in this way. The closest to it I can
think of is in college, a course that included group theory, we
were sent to the chalk board to try to invent groups of various
sizes up to 5. For 1,2,3,4 it was easy, pretty obvious. But for 5
it was hard, there seemed to be only one possible group structure.
Anything else violated associativity. The lesson was indeed the
cyclic group is the only group of order 5. So this chalkboard
lesson got our minds prepared to really appreciate the power of
subgroups and cosets in narrowing down the possibilities. In this
case, some power of an element must be equal to 1, so that element
generates a cyclic subgroup of size equal to that power number. But
by cosets the order of the whole group (5) must be divisible by the
order of that subgroup, but because 5 is prime you have only two
choices, whole group cyclic, or the trivial case that you are
looking at the identity. Thus any non-identity element must
generate cyclic subgroup of size 5, which by pidgenhole principle
must be whole group, QED.
Then we did groups of order 6, which was *much* easier knowing
already about cosets and what they imply about subgroups.
(And we got the lesson that not all groups are commutative!)
[...] I remember the algorithm was rather obvious: [...]
Quite so! Lots of science in general, and maths/CS in
particular, is rather obvious. The job of education is to make
it so. *Before* you've been taught how to make things obvious,
even the simplest concepts are obscure.
But I wasn't *taught* how to do binary search. Somehow I heard of
the general idea of splitting in the middle, and figured out myself
the actual algorithm, which at that point (with a little thought)
was obvious (to me).
If LO>HI then your range is empty, which means you've already
bottomed out without finding the target, so you immediately
return a not-found indication, for example -1.
You've already hit a design problem! What will you do if -1 is a
permitted index?
This is the first of the two good points you raise, where the
conditions of the system where I worked meant "no problem". In this
case, I was programming in assembly language, where all array
indexes start at 0, or in fortran where all array indexes start at
1, or in SAIL where I forget but it was one or the other. So -1 was
always smaller than the bottom index.
Do you want the complexity of returning a structure consisting of
a Boolean and an integer [if your chosen language permits that]?
None of the languages allowed that. But assembly language allowed
using more than one return-value register, so in that case it would
have been possible. But there's no point since the test of the
boolean register to see whether it's nonzero isn't any faster than
the test of the main register to see whether it's -1 or not (either
is two instructions, compare register against literal constant to
set status bits, then conditional branch), so multiple-value-return
was no advantage, given that a single out-of-bounds value was
always available to use as a not-found indication.
Or do you want the caller to have to test whether the returned
index is in range?
All it has to test is that one globally defined not-found value.
Depending on the language, that could be a named constant in
memory, a macro, or if neither available I could just remember to
always test for any negative number by testing for retval<0 instead
of retval=-1.
But since the caller *must* check the returned whatever (value,
values, structure) for found/notfound, it doesn't matter whether we
use structure or multiple register values or single encoded value,
it's all the same amount of code in any case, and using a single
encoded value is simplest and most general (same encoding scheme
works in all three languages, so I don't have to remember which I'm
using as I switch around between languages).
As for using non-local return, such as throw/catch or
error/errorset, I didn't get access to a decent Lisp until many
years later, and by then I was entrenched in the
encoded-single-return-value method, so I kept using it there too.
(Except in LISP I can use NIL instead of -1 as not-found value.)
Otherwise you compute MID = (LO+HI)/2 (doesn't matter which way
you round, you can even be inconsistent from moment to moment,
the algorithm works in any case).
[The algorithm works, of course, as long as LO <= MID <= HI, it's
just more efficient if MID is somewhere around the middle.
Well, that's the whole point of *binary* instead of *sequential*
search, isn't it? Divide and conquer works best if you divide in
half as closely as is practical. Any near-mid-point, even as far
away as 25/75 quadrile (is that the right word??) would still
guarantee log(n) time with only moderately worse constant factor.
But midpoint is easier/faster to compute than any other such
splitting point, so it'd be perverse to deliberately pick a
worse-than-middle splitting point.
But if we're picking nits, then you're in trouble if LO+HI >
Maxint, or in various other similar potential overflow cases.]
I thought of that as I was posting my algorithm, but I wanted to
stay honest as to my original algorithm, and have it appear nice
and symmetric instead of weird. In fact I was working on a PDP-10
computer which used 36-bit words for integers (and floats too, but
I never used them for such purposes), but only an 18-bit address
space, so even if all of memory was one array the index never
exceeded the right half of one machine word, so there was never any
problem with overflow when adding two or even a hundred array
indexes in a single word of memory.
Of course if you're right up at the limit where twice an array index
might overflow (wrap around to negative value), you have to change
mid := (lo+hi)/2
to:
mid := lo + (hi-lo)/2
which takes longer to compute so it's not used unless the machine
architecture and programming environment present this problem.
Of course there are three other ways to accomplish the same
avoid-overflow/wraparound trick:
mid := hi - (hi-lo)/2
mid := lo - (lo-hi)/2
mid := hi + (lo-hi)/2
but I discourage any of those because they unnecessarily complicate
the debugging with generation of negative differences and/or
backward offsets, which nobody really bright would ever get wrong,
but (wink wink). Just asking for a stupid oversight to break
everything, or a new programmer on the job to fail to understand it
and change it and break it.
Now if this algorithm were written in C++ templates (or C macros,
yuk!!), where the person writing the algorithm has no control over
what data types and array ranges will occur when it's used, then
it'd be really hard to get a single algorithm that is **correct**.
For example, if array indexes are of type unsigned integer, then
there's no such thing as -1 as return value. However we can
probably assume that array indexes are closed under subtraction of
smaller value from larger value in all cases, so at least that one
of the two possible problems isn't a problem, so long as we stick
to lo+(hi-lo)/2, avoiding the three alternatives I said I
discourage. For a template/macro description of the algorithm to be
universally correct, the not-found constant will probably have to
be supplied as an extra parameter (argument) supplied by the
calling application. Some applications that use signed integers but
have arrays always start at 0 might prefer -1 for not-found, while
other applications that use unsigned integers might use initialHI+1,
different value for each call, or maxPosInt, different value for
each index datatype, as the not-found value, but hey it works!
And of course in Java you could use the LISP trick, pass back a
polymorphic data type, and do a type-check to see whether the value
you got is of the index type or of the exceptional type. That
specific not-found value would of course be passed as a parameter
to the binary search routine. (Or maybe better, throw a real live
exception!! Java has a pretty nice exception-class and
exception-handling system built-in from the start.)
- If target smaller, tail-recurse with LO, MID-1, or if you're
doing it iteratively then do assignment HI := MID-1. [...]
In the old days, this wasn't necessarily as easy as you make it
seem. For integer elements, OK.
That's all I ever worked with in regard to binary search.
For reals, there was the permitted error to worry about.
If I had written floating-point binary search, I probably would
have always returned the *closest* match, a final fixup on the
index just before returning, never returning a not-found value, and
then let the caller decide whether the value was close enough for
his needs or not. If I wanted that for integers, that would have
been an interesting varition too, useful for some applications.
Few languages had proper strings before the mid-'60s,
Indeed I started using SAIL in 1969, which misses that time period
by a few years. I didn't know about Lisp until Larry Masinter
showed it to me circa 1972, but it had strings effectively as lists
of ASCII numeric codes from the beginning (1964, one of the "few"
you cite I presume), or as pnames of symbols as an alternative,
either of which was good enough for hacking an algorithm.
so if you had an application like trying to see if a word was in
a list, there was a lot of encoding and decoding to do here.
I cheated, using a purturbed linear-congruential algorithm to
compute 35-bit hash of the string, then comparing the hashs. There
was "never" two strings with the same hash, until I implemented
Schroeppel's linear-relation-finding algorithm in MacSyma,
whereupon it was easy to put in the linear constraints for a
hashing conflict and find smallest-norm five-character
string-differences that generated zero hash difference, and then
use one of those to directly construct pairs of strings with the
same hash, sigh.
Many languages didn't permit recursion;
Yeah, like Fortran, or anything whatsoever using IBM 360 calling
conventions where each routine had its own private static block for
storing the saved registers. But iteration was always allowed, and
as I pointed out either could work the same way, either recurse
with LO,MID-1, or assign HI:=MID-1, so that's not a problem.
and even "iteration" was discouraged -- "while (lo >= hi) {...}"
is a relatively late invention
I agree syntactically it's moderately recent. It was in Lisp, but I
probably programmed binary search before I met Lisp. But if all you
had was FOR loops, with RETURN any time you wanted to break out of
the loop, you could set up a worthless FOR loop (ran virtually
forever, longer than log(n) for sure), and thereby emulate "while
true" for the duration of the binary search.
so you got spaghetti code using "goto" to emulate the iteration.
That's not spaghetti code. This is nice clean programming template:
FUNCTION functionname (parameters) BEGIN
declare local constants and variables.
initialize loop constants.
LP:
test data conditions, and conditionally:
perform changes to loop variables, or
return a value already now, or
go to EX.
GOTO LP;
EX:
Final fixup of return value (code common to more than one exit path).
Return that value now.
END;
Spaghetti code is when you have more than one non-final label in a
single block and you jump around between them in a non-structured
way. For example, the parser for Reduce (Tony Hearn at Utah) was
one huge spaghetti-code function about five or ten pages long.