Contributor Post Created with Sketch. Recommended by Ricochet Members Created with Sketch. How to Build a Computer 11: The Binary Search Algorithm

 

We’re taking a break from the manufacturing process to cover some ideas in programming. Algorithms, what that means and why. Sounds fancy, doesn’t it? It ain’t as bad as it sounds. Let’s jump right in:

What’s An Algorithm?

It sure as heck ain’t Al Gore’s killer dance moves. The word “Algorithm” means something like a recipe. It’s a series of rules, and if you follow the rules you get the promised result. Computer jerks talk about them because you have to break your instructions down into very simple bits in order to make a machine understand what it needs to do. Let’s try a very simple algorithm.

The MakeStuffBigger algorithm; pass in stuff, get bigger stuff out.

  1. Pass in some stuff
  2. Add one to it.
  3. Return your enbiggened stuff.

That’s all it takes. You MakeStuffBigger on 17 and you get 18 out of it. This is the sort of thing a third grader uses when he’s saying “nuh-uh infinity-plus-one times!”, a practice upon which I’ve discoursed previously.

You can see how the recipe comparison works; a recipe is an algorithm for making a food. Let’s take a look at that.

The PizzaMe algorithm; Pass in dough, sauce, cheese, and one or more toppings. Returns one Pizza

  1. Roll out pizza dough so it’s flat.
  2. Apply sauce.
  3. Apply cheese.
  4. Apply more cheese
  5. Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?
  6. For Each topping in [Set of Toppings] apply Topping to pizza.
  7. Preheat oven to 400 degrees Freedom (254 Commie)
  8. Once oven is at temperature insert pizza
  9. Bake for 20 minutes
  10. Remove pizza from oven.

Notice anything? The preheating instruction comes in at step 7. Odds are you were already thinking you should start the oven at step one so you don’t have to wait so long. The oven can be warming up while you’re mucking about with the cheese. That’s the thing people generally worry about when they’re talking about algorithms; which one is quicker. Both the original and revised PizzaMe algorithms will produce a Pizza, just one is quicker.

You could also apply a layer of abstraction to this:

EasyPizzaMe: Pass in Cash, returns one Pizza

  1. Call for delivery

The PizzaMe algorithm is still happening, it’s just happening at the pizza joint. You’ve abstracted past the point where you have to worry about those details. Neat, huh?

Okay, but back to computers.

What’s a Binary Search?

What’s a search? You’re looking through a thing to find another thing. Let’s say you’re looking for my house in Eau Claire Wisconsin. Here’s one way you could go about it.

  1. Find a house in Eau Claire. Knock on the door.
  2. If I answer the door you’re done.
  3. If I don’t then find another house and check that one.

Not terribly efficient, and that’s even assuming I’m sociable enough to answer random door-knockers. Eventually it’d get the job done though. You could make it a little more efficient (3. Ask that guy if he knows Hank) but it’s still slow. But hey, Eau Claire only has like 60,000 people, if you set a computer to do it it’ll be quick enough. It’s not you knocking on those doors after all.

Let’s modify the parameters. Supposing I lived in New York City. At ten million folks it’s much less likely that your computer will perform this search in a reasonable amount of time. (Reasonable defined as ‘I’m getting bored over here!’ It’s actually a pretty useful standard.) Now suppose you don’t actually need to get to my house, you just need my phone number. You could look in the phone book. (I don’t have a land line, but my NYC alter-ego does. That guy’s a dork.)

Simple phone book search: Pass in a name, get out a phone number

  1. Look at the first entry.
  2. If it’s Hank Rhody you’re done.
  3. If it isn’t, look at the next entry.

Still going to take a while, even for a computer. That half second while it’s thinking is enough for me to refresh my Ricochet alerts and get distracte. But hey, phone books are alphabetical by last name. Let’s try again, using that information:

  1. Open the book to the middle. Check any name on that page.
  2. If it’s Hank, you’re done (lucky you!)
  3. If it isn’t, check whether it’s alphabetically before or after it. Probably before; R is towards the end of the alphabet.
  4. Stick your thumb in the book at that page. Open the phone book halfway between your thumb and the correct end of the book.
  5. Repeat.

Each time you’re halving the amount of names you’d have to look through. Even if you’re doing it stupidly you’re going to get to my name after something like thirty checks. It’s a little more complicated than check each name in order but it’s much quicker.

That’s a binary search algorithm; “Binary” means you’re splitting the dictionary in two. It’s pretty quick; it’s possible to make quicker algorithms but they get more complex, and I’ve never needed them at the scale I work. I only got into binary searches because the “check each one” was taking too long. I had an Excel file with a big table (~250k lines, at that time) that I wanted to match times against. Here’s a function I wrote in VBA to do just that.

MatchTimeToTable: Stick in a time, returns the row of the table that contains that time.

“hi” is the highest number line you’re considering, “lo” is the lowest number. Naturally midPt is the middle-est.

Does it make sense? Probably not just from reading through it. I’ll work out an example for you. Let’s say I’m looking between rows 2 and 200,000 for a value. Eventually I’ll find it in the slot 31,337. Here’s a walk-through of what happens:

Calculate midPt (99,999).
Is it correct? No.
Is the guess too small? No.
Then the guess is too big; reset the top row to 99,998 (the next smallest row after the guess) and try again.

Calculate midPt (49,999). Too big again.
Reset and calculate midPt again. 24,999. Too small. Adjust the lower bound this time to 25,000, and calculate it from there.

Calculate midPt again (49,999 – 25,000)/2 + 25,000 = 37,498 (That’s a slightly unusual calculation for an average. The minus/plus bit is to avoid the number getting temporarily too big and breaking things.)

37,498 is too big again. Reset your upper bound and calculate it again. Now we’re checking between 25,000 and 37,497.
Repeating, we get approximately 31,250 (close!), 34,375 (further), 32,750, 32,000, 31,650, 31,450, 31,350, 31,300, 31,325, 31,337

Without cooking the example we found one value in 200,000 in only fourteen guesses. Lighting quick! Okay, I may have rounded for ease in the later calculations; I was doing this manually. You get the point though; having a clever algorithm makes doing your job immensely quicker. Quicker enough to make a difference? It helped quite a bit with my particular problem. But elsewhere?

Why’s an Algorithm?

Once upon a time I was studying thickness of a polyimide film on stainless steel. Had to do with process development. I had a measurement machine and I wasn’t sure I trusted the output of it’s program. Found a way to export a list of coordinates. Three hundred and sixty thousand lines of X, Y, and Z positions. Okay, I can make a visual map of that stuff in an Excel sheet. My first pass at an algorithm was stupid; with nested loops. It’d run through the whole list once for each item in the list. Worse than that; I was asking it to do calculations proportional to the cube of the lines in the table. At least 2,000,000,000,000,000 number crunches. That’s a number so large the national debt hasn’t even reached it yet. Even with Moore’s law at my back I wasn’t going to finish that calculation. 

Second pass at the algorithm was less stupid. It only looped through the list once, which meant that I was only asking it to perform on the order of 360,000 calculations. That’s a number so small the federal government spends it without noticing. But I’m just a hedge programmer, playing in Excel while the real programmers are out writing code in hexadecimal. What does this kind of stuff look like in the real world?

Let’s say you’re looking for a unique phrase on every web page on the internet. You go to Google and plunk in the name Claymore J. Flapdoodle and see what it spits out. It tells me “About 16,100 results (0.55 seconds) “. Google has an algorithm that it uses to search the whole internet, categorize results, and show you the best ones, and do it all in half a second. That isn’t (just) rooms and rooms of computers. I don’t know how they do it, but it’s a heck of a lot more complex than a binary search. Google’s search algorithm is one of the most valuable bits of intellectual property in the world. Now you can understand why. The difference a good algorithm makes is the difference between half a second and half a century.

I hope you’ve enjoyed our little interlude into logic. I’ll get back to exposing next week (swearsies) once I’ve gathered some more pictures. Join us next week for “The Terrible Truth of the Autoexposer — Revealed!” or “Freaking Finally”.

This is part eleven of my ongoing series on How to Build a Computer, the “That’s not a Knife” way. You may find previous parts under the tag How to Build a Computer. This week’s post has been brought to you by Eggrolls Plus. The Plus is good too, but you’ll never know it because you’ll love our eggrolls so much. Eggrolls Plus!

[First] [Previous] [Next]

There are 32 comments.

Become a member to join the conversation. Or sign in if you're already a member.
  1. RightAngles Member

    You can put these all together and make them into a book

    • #1
    • August 12, 2018, at 12:19 AM PDT
    • 3 likes
  2. Arahant Member

    Hank Rhody, Probably Mad: Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?

    Gonna have to go deep-dish to fit enough cheese in there.

    • #2
    • August 12, 2018, at 12:26 AM PDT
    • 3 likes
  3. Gary McVey Contributor
    Gary McVey Joined in the first year of Ricochet Ricochet Charter Member

    RightAngles (View Comment):

    You can put these all together and make them into a book

    Hank really could! This is wonderfully written. 

    • #3
    • August 12, 2018, at 1:25 AM PDT
    • 2 likes
  4. Randy Weivoda Moderator
    Randy Weivoda Joined in the first year of Ricochet Ricochet Charter Member

    Hank Rhody, Probably Mad:

    What’s An Algorithm?

    It sure as heck ain’t Al Gore’s killer dance moves.

    Oof. Did @samrhody help you write that one?

    Hank Rhody, Probably Mad: Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?

    Alright, you’re forgiven.

    • #4
    • August 12, 2018, at 9:07 AM PDT
    • 4 likes
  5. Judge Mental, Secret Chimp Member

    Hank Rhody, Probably Mad: The difference a good algorithm makes is the difference between half a second and half a century.

    One of these days, I need to write a post on the Texas Two-Step. My favorite ever algorithm.

    • #5
    • August 12, 2018, at 9:50 AM PDT
    • 4 likes
  6. Sam Rhody The Insane Member

    Randy Weivoda (View Comment):

    Hank Rhody, Probably Mad:

    What’s An Algorithm?

    It sure as heck ain’t Al Gore’s killer dance moves.

    Oof. Did @samrhody help you write that one?

    Hank Rhody, Probably Mad: Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?

    Alright, you’re forgiven.

    I wish I could take credit for that. 

    • #6
    • August 12, 2018, at 9:58 AM PDT
    • 6 likes
  7. Matt Saracen Coolidge

    Hank Rhody, Probably Mad: Preheat oven to 400 degrees Freedom (254 Commie)

    Gas 6 in Brit. Why they use that particular scale is beyond me, but I have a couple of British cookbooks so I had to figure it out.

    • #7
    • August 12, 2018, at 5:21 PM PDT
    • 2 likes
  8. Jimmy Carter Member
    Jimmy Carter Joined in the first year of Ricochet Ricochet Charter Member

    Hank Rhody, Probably Mad:

    • Preheat oven to 400 degrees Freedom (254 Commie)

    That cracked Me up.

    • #8
    • August 12, 2018, at 5:25 PM PDT
    • 3 likes
  9. Matt Saracen Coolidge

    This binary search algorithm sounds suspiciously like Newton’s Method for calculating square roots:

    1. Guess.
    2. Square it.
    3. Is it right?
    4. Yes? You’re done.
    5. No? Too big or too little?
    6. Add or subtract from your original guess.
    7. Repeat.

    Which is so simple that I got a B on my first Calc II exam in college because my handwriting made it look like I’d written x*2 instead of x^2, and I was in such a hurry to finish the exam I failed to check my work, and didn’t notice that I’d calculated the square root of 65 to be roughly 11.

    (In my defense, I learned the night before the final that the only reason the girl in my recitation I had a major crush on finished the exam questions was that she picked one of the five problems on each exam and skipped it! I wish I’d taken her advice on the final, but I was honestly still very excited that she’d come to my room the night before and asked me to tutor her in Econ. That she wrote me over Christmas Break to tell me she’d gotten all As for the semester, whereas I got Bs in both Calc II and Econ, actually made her more attractive, not less.)

    • #9
    • August 12, 2018, at 5:28 PM PDT
    • 7 likes
  10. Hank Rhody, Badgeless Bandito Contributor

    Sam Rhody (View Comment):

    Randy Weivoda (View Comment):

    Hank Rhody, Probably Mad:

    What’s An Algorithm?

    It sure as heck ain’t Al Gore’s killer dance moves.

    Oof. Did @samrhody help you write that one?

    Hank Rhody, Probably Mad: Look, I’m from Wisconsin, you’re not getting out of this until there’s enough cheese on that pizza, get me?

    Alright, you’re forgiven.

    I wish I could take credit for that.

    I think I first heard it in the early 2000’s, on a cheap gag web site. It featured a dancing Al Gore. Nuff, as the kids say, said.

    • #10
    • August 12, 2018, at 7:36 PM PDT
    • Like
  11. Hank Rhody, Badgeless Bandito Contributor

    dnewlander (View Comment):

    Hank Rhody, Probably Mad: Preheat oven to 400 degrees Freedom (254 Commie)

    Gas 6 in Brit. Why they use that particular scale is beyond me, but I have a couple of British cookbooks so I had to figure it out.

    Do they also measure their food weights in stones?

    • #11
    • August 12, 2018, at 7:40 PM PDT
    • 3 likes
  12. Arahant Member

    Hank Rhody, Probably Mad (View Comment):
    Do they also measure their food weights in stones?

    That would be a lot of food to make it worthwhile.

    • #12
    • August 12, 2018, at 7:42 PM PDT
    • 2 likes
  13. Hank Rhody, Badgeless Bandito Contributor

    dnewlander (View Comment):
    (In my defense, I learned the night before the final that the only reason the girl in my recitation I had a major crush on finished the exam questions was that she picked one of the five problems on each exam and skipped it! I wish I’d taken her advice on the final, but I was honestly still very excited that she’d come to my room the night before and asked me to tutor her in Econ. That she wrote me over Christmas Break to tell me she’d gotten all As for the semester, whereas I got Bs in both Calc II and Econ, actually made her more attractive, not less.)

    Yeah, it’s similar. I once spent a long night at the plastics factory working out the square root of five by hand using Newton’s method. I got it wrong.

    Wish I had as good an excuse as a girl.

    • #13
    • August 12, 2018, at 7:44 PM PDT
    • 2 likes
  14. Arahant Member

    Slide rules, guys.

    • #14
    • August 12, 2018, at 7:50 PM PDT
    • 1 like
  15. Judge Mental, Secret Chimp Member

    Good definition of algorithm, by the way. Although, it’s kind of fun to hear people using the word when they obviously don’t know the meaning. Most people think it’s some kind of magical incantation.

    • #15
    • August 12, 2018, at 8:06 PM PDT
    • 5 likes
  16. Matt Balzer, Imperialist Claw Member

    Judge Mental (View Comment):

    Good definition of algorithm, by the way. Although, it’s kind of fun to hear people using the word when they obviously don’t know the meaning. Most people think it’s some kind of magical incantation.

    Sufficiently advanced technology!

    • #16
    • August 12, 2018, at 8:11 PM PDT
    • 5 likes
  17. Hank Rhody, Badgeless Bandito Contributor

    Judge Mental (View Comment):

    Good definition of algorithm, by the way. Although, it’s kind of fun to hear people using the word when they obviously don’t know the meaning. Most people think it’s some kind of magical incantation.

    I wrote a paper in college on how you could replace the witches in Macbeth with computer programmers. When you get right down to it ‘magic incantation’ is a pretty good description.

    • #17
    • August 12, 2018, at 8:12 PM PDT
    • 5 likes
  18. LC Member
    LC Joined in the first year of Ricochet Ricochet Charter Member

    Now this is my zone. 

    • #18
    • August 13, 2018, at 10:21 AM PDT
    • 5 likes
  19. Hank Rhody, Badgeless Bandito Contributor

    LC (View Comment):

    Now this is my zone.

    And suddenly I’m worried.

    One of the hazards I took into account when I started writing this series, there are an awful lot of smart people on Ricochet. Sooner or later I’m going to get something wrong, and what’s worse, something that’s blatantly, awfully wrong in front of someone who happens to know everything there is to know about the subject.

    On the subject of algorithms generally, some comments in my code:

    Public Sub BinaryArraySort(ByRef someArray, Optional isNumeric As Boolean = False)
    ‘Sort an array using binary search algorithms.
    ‘Ought to be quicker than the bubble sort up above for large arrays
    ‘however since I’m making this up as I go, don’t be too sure of that.

    • #19
    • August 13, 2018, at 10:39 AM PDT
    • 7 likes
  20. LC Member
    LC Joined in the first year of Ricochet Ricochet Charter Member

    Hank Rhody, Probably Mad (View Comment):

    LC (View Comment):

    Now this is my zone.

    And suddenly I’m worried.

    One of the hazards I took into account when I started writing this series, there are an awful lot of smart people on Ricochet. Sooner or later I’m going to get something wrong, and what’s worse, something that’s blatantly, awfully wrong in front of someone who happens to know everything there is to know about the subject.

    On the subject of algorithms generally, some comments in my code:

    Public Sub BinaryArraySort(ByRef someArray, Optional isNumeric As Boolean = False)
    ‘Sort an array using binary search algorithms.
    ‘Ought to be quicker than the bubble sort up above for large arrays
    ‘however since I’m making this up as I go, don’t be too sure of that.

    What you’ve written up is perfectly fine. Nice bit with abstraction.

    I’ve always found this visualization below to be interesting. Poor bubble sort. 

    • #20
    • August 13, 2018, at 11:24 AM PDT
    • 4 likes
  21. Matt Saracen Coolidge

    LC (View Comment):

    Hank Rhody, Probably Mad (View Comment):

    LC (View Comment):

    Now this is my zone.

    And suddenly I’m worried.

    One of the hazards I took into account when I started writing this series, there are an awful lot of smart people on Ricochet. Sooner or later I’m going to get something wrong, and what’s worse, something that’s blatantly, awfully wrong in front of someone who happens to know everything there is to know about the subject.

    On the subject of algorithms generally, some comments in my code:

    Public Sub BinaryArraySort(ByRef someArray, Optional isNumeric As Boolean = False)
    ‘Sort an array using binary search algorithms.
    ‘Ought to be quicker than the bubble sort up above for large arrays
    ‘however since I’m making this up as I go, don’t be too sure of that.

    What you’ve written up is perfectly fine. Nice bit with abstraction.

    I’ve always found this visualization below to be interesting. Poor bubble sort.

    I remember having to write all of those sorts in high school (in Pascal!) just to prove that quicksort was fastest (because we didn’t have YouTube in 1985).

    By the time I was in college, they didn’t even bother with that exercise, merely telling new programmers, “Use Quicksort. It’s the fastest.”

    • #21
    • August 13, 2018, at 11:45 AM PDT
    • 4 likes
  22. LC Member
    LC Joined in the first year of Ricochet Ricochet Charter Member

    Hank Rhody, Probably Mad (View Comment):

    Judge Mental (View Comment):

    Good definition of algorithm, by the way. Although, it’s kind of fun to hear people using the word when they obviously don’t know the meaning. Most people think it’s some kind of magical incantation.

    I wrote a paper in college on how you could replace the witches in Macbeth with computer programmers. When you get right down to it ‘magic incantation’ is a pretty good description.

    I guess I’ll take that as a compliment. I always liked those witches. 

    • #22
    • August 13, 2018, at 3:21 PM PDT
    • 4 likes
  23. Belt Member

    Just wait until you get to deal with 1) recursion and 2) random number generators.

    • #23
    • August 13, 2018, at 3:49 PM PDT
    • 1 like
  24. Matt Saracen Coolidge

    Belt (View Comment):

    Just wait until you get to deal with 1) recursion and 2) random number generators.

    I had the “random” number table on my Atari 800XL memorized, and I could give a pretty good guess as to what number was going to come up based on how long it had been since I reset the computer.

    Yes, I spent hours writing programs to POKE random values into every memory location to: a) see what interesting stuff I could get on the screen, and b) see how long it would take to hang the computer. Didn’t everyone?

    • #24
    • August 13, 2018, at 4:13 PM PDT
    • 4 likes
  25. Hank Rhody, Badgeless Bandito Contributor

    Belt (View Comment):

    Just wait until you get to deal with 1) recursion and 2) random number generators.

    Missed opportunity there. Could have been ” and 17) random number generators.”

    I am looking forward to getting to random number generation. There’s quite a bit there that I don’t know or don’t understand yet, and I get to learn it before I can present it to y’all.

    • #25
    • August 13, 2018, at 4:15 PM PDT
    • 3 likes
  26. Gary McVey Contributor
    Gary McVey Joined in the first year of Ricochet Ricochet Charter Member

    dnewlander (View Comment):

    Belt (View Comment):

    Just wait until you get to deal with 1) recursion and 2) random number generators.

    I had the “random” number table on my Atari 800XL memorized, and I could give a pretty good guess as to what number was going to come up based on how long it had been since I reset the computer.

    Yes, I spent hours writing programs to POKE random values into every memory location to: a) see what interesting stuff I could get on the screen, and b) see how long it would take to hang the computer. Didn’t everyone?

    I had an 800XL too. Quite a bargain for its time. 

    • #26
    • August 13, 2018, at 4:27 PM PDT
    • 2 likes
  27. Arahant Member

    Belt (View Comment):

    Just wait until you get to deal with 1) recursion and 2) random number generators.

    Those are both fun!

    • #27
    • August 13, 2018, at 4:50 PM PDT
    • 1 like
  28. SParker Member

    Hank Rhody, Probably Mad (View Comment):
    Yeah, it’s similar. I once spent a long night at the plastics factory working out the square root of five by hand using Newton’s method. I got it wrong.

    You discovered the need for a sanity check. After 20 or so iterations you should have been asking: Do I have OCD? If you’re next question was “But do I have OCD?” and the question after that, and the question after that … then the answer is: Yes. Yes you have. Seek treatment. Although, in rare cases, you simply have a case of Hamlet’s syndrome, which is easily treated by one-time application of a poisoned sword.

    • #28
    • August 13, 2018, at 7:25 PM PDT
    • 6 likes
  29. The Reticulator Member

    Hank Rhody, Probably Mad (View Comment):

    I wrote a paper in college on how you could replace the witches in Macbeth with computer programmers. When you get right down to it ‘magic incantation’ is a pretty good description.

    You’re going to post that paper here, right?

    Please?

    • #29
    • August 13, 2018, at 10:03 PM PDT
    • 3 likes
  30. Hank Rhody, Badgeless Bandito Contributor

    The Reticulator (View Comment):

    Hank Rhody, Probably Mad (View Comment):

    I wrote a paper in college on how you could replace the witches in Macbeth with computer programmers. When you get right down to it ‘magic incantation’ is a pretty good description.

    You’re going to post that paper here, right?

    Please?

    Don’t believe I have it anymore. If I do it’s locked away on an old hard drive in a dusty box.

    The assignment was to change the setting of the play and see what that does to the story. Probably the silliest was the Stoner Macbeth.

    “Dude, I know what I saw, and those trees were moving.”
    “Been smoking some of that Birnam Wood?”

    • #30
    • August 14, 2018, at 7:10 AM PDT
    • 8 likes

Comments are closed because this post is more than six months old. Please write a new post if you would like to continue this conversation.

Join the Conversation Created with Sketch.
Have Something to Say?

Join the Conversation