Binary Search implementation issues

When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it,[44] and another study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.^[45] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.^[46]

https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_

So designing and writing provable correct software is hard. Thanks for the news.

Most programmers are brainlets.

perl -lne 's/[^01]//g; print if /[01]+/'

quite incredible!

even trying our best, it's this difficult to get simple things right.

I wonder if we now have tools that would help write small functions like this better?

Thats why unit testing was invented.
Also if i had to code when other people look at me, i'll probably write shit code. I can't work under stress.

>>5
You have a tool, it's in your skull.

>>2
...but apparently most people don't make use of this tool.

>>6
Testing doesn't work when you don't even know what to test.

The underlying problem here is that people don't know how to use induction and handle the four cases in total: even-length array, not found; even-length array, found; odd-length array, not found; odd-length array, found.

Binary search sounds deceptively simple: cut the array into two halves, look at the "middle" element and continue with either half if it's not found, until you get down to 1 element. People execute this "algorithm" IRL without realising one key mistake in that description: there is no "middle" element if the length is even, and they're actually looking at an element in either the lower or upper half.

As for the overflow "bug"? It only happens with extremely large arrays. Maybe it was known that it would overflow, but was not a problem because searching an array of 2G elements binarily is just not something done often or even the best way to solve the problem. With 64-bit, the overflow becomes expoentially harder and so I would not consider it a "bug" at all, just an implementation limitation. No one is creating, much less searching arrays of 2^63 elements binarily.

Still i prefer C integer promotions over "Garbage-Collected Integers".

>>8
If you think the only alternatives are C retardation and ``"Garbage-Collected Integers"'' then you've been swindled by your school.

Then people wonder why someone from India who literally defecates on the street and learned Microsoft BASIC for MS-DOS without a computer knows more about computer science and is better qualified for a job than hipster ``goyim'' who read dumbed down books like SICP.

>>7
kill yourself

>>10
Check 'em!

>>9
Computer science isn't about programming or computers. It's totally legitimate for anybody to study computer science with or without the help of BASIC and MS-DOS. You don't even need to touch a computer to study computer science.

>>12
It's not science if you don't make empirical observations of real world behavior.

>>13
Computer Science is a religion?

>>12

In my dictionary, the preferred definition of science involves discovering
properties of the natural world. Engineering involves the application of those
properties to solve practical problems. By those definitions we are neither
scientists nor engineers. The principal objects of our study are manmade, not natural.
--William Allan Wulf, inventor of BLISS programming language, president of the National Academy of Engineering, Professor of Engineering and Applied Sciences

>>13
>>14
Computer science is not about computers nor is it a science. The name is actually a misnomer like "geometry"

>>15
science - discovering properties of the natural world.
engineering - the application of those properties to create new/desired natural &/or artificial properties

philosophy - the study of things which need not exist in physical forms. For instance, science is not an object that science can observe and study.

Computer Algorisophy

Computer Religion:
Have you Read your SICP today?
Designs Patterns you must follow or else

Primitive Computer Worship:
Retrocomputing

Computer Philosophy:
http://c2.com/cgi/wiki?WelcomeVisitors

Computer Art:
The Art of Computer Programming
Art of Assembly
Demoscene

Computer Science:
https://arxiv.org/archive/cs/

>>18
Computer Literature:
WEB
Inform

Computer Postmodernism:
Esolangs
Langsec

>>18

c2.com

Back to reddit.com/r/tvtropes, please!

>>20
epic meme!

>>22
epic dubs!

>>21
Thanks, buddy!