« Peaceful Stories from a Distant War | Main | Kofi Awoonor and Westgate »

September 26, 2013

Comments

Megan McArdle justifies farm subsidies to dead people because they do something to get their piece of teh American Dream.

Open thread? Okay. I have an academic question for the computer scientists who hang around here.

I did a bit of programming during my engineering studies, as was required. One of the things I learned about was the binary search (of course - in fact, I may have first seen it in high school). I've always "liked" the binary search for its conceptual simplicity and its seeming efficiency. The rub is - what do you really do with it?

The best practical example I've found was in playing the High-Low Game on The Price is Right (not that I've ever been a contestant, mind you). I haven't actually watched The Price is Right in years, mainly because I have far better things to do, since becoming a reasonably functioning adult at some point (I guess).

But back when I did watch The Price is Right, the High-Low Game was the most frustrating to watch because most of the contestants were just so, well...I don't want to say "stupid" about it, so let's go with "un-systematic." I mean, if you used a binary search, you could find the correct price in short order without even knowing what the item in question was.

It was the one game, or at least one of the few games, with no element of randomness to it. You didn't need any luck, and could guarantee yourself a win purely by your own actions. Just start with a guess of, say, $5000 and execute the search.

Being a human, and not a computer, you wouldn't even have to stick to the formality of the exact halving of intervals. Use rounder numbers to keep it simple, so long as they're reasonably close to the middle. And once you get within smaller ranges, you can just go up or down by hundreds or tens, just to avoid getting too caught up in computation and screwing up under pressure (getting "turned around" so to speak).

With that, what practical applications are there to a binary search? Aside from a game where you're searching for a value that someone else, like Bob Barker, knows but won't tell you, what do you do with it? Usually, you aleady know the value you're looking for, but you're just trying to find out where it is.

Looking for examples on-line returns things that look like the problems we did in school. They're just contrivances to explain how the search works rather than real-world examples of what someone would actually use a binary search for.

The best analogy I've seen is looking up someone's phone number in a phone book. It's not exactly a binary search, but you start with a guess at a page and go forward or backward depending on where you are alphabetically. I that case, you're not really looking for the person's name, since you already know it. You're looking for the phone number. So I'm guessing that binary searches are just ways of looking at databases with some sort of indexing to find a value associated with some other piece of information you need.

Say I have a Social Security number and I need to know whose number it is. All the SSNs are listed in a database in numerical order and are associated with names. If I can find out where the SSN number is, I can find the name.

But is that kind of it? Is there something more than that? Is it something that isn't really used all that much in practice, but that makes for a good teaching tool? I could see it going either way - something the modern world couldn't do without, or something they mostly just teach in school.

So I'm guessing that binary searches are just ways of looking at databases with some sort of indexing to find a value associated with some other piece of information you need.

exactly.

while situations like that don't come up every day, a binary search is indispensable for such situations.

they're also useful if you have a sorted list of items and you have something which could be one of those items (ex. a dictionary and a random string of characters - is it a word?, a list of employee SSNs and a random digit number - is it an employee's SSN?, zip codes, etc.). a binary search is a quick way to search your list to see if your test item is a member of the list.

there are ways to optimize such searches search so that it goes faster, of course.

a random digit number = a random nine digit number

Breaking: Twitter allows Obama special character allotment! May exceed 140 limit! No special allotment for GOP!

The PIR game I was thinking of was actually The Clock Game. There is a Hi Lo Game, which is completely different. All according to Wikipedia, natch.

such searches search so that it

feh

blogs with editable comments have utterly destroyed my ability to get things right the first time.

Whereas blogs with NON-editable comments have destroyed the ability to get things right, EVAR

On the bright side, reading non-editable comments has desensitized me to things that aren't completely right. It's like reading Shakespeare. Don't get too caught up the individual words. Just take the whole thing in a go with it.

There's what's right and there's what's right, and never the 'tween shall meet.

http://dish.andrewsullivan.com/2013/09/26/the-gops-demands/

Yikes! That bridge goes way up high and always made me nervous, even though it has a nice view looking north at Green Bay (the Lake Michigan feature,not the city, which is south of the bridge.) The Frigo cheese factory is right beside the cheese outlet store in Lena, Wi. We like to stop there and get the smoked string cheese whips.

That statement by McNealy is astonishing.

"Instead of doing the $800 billion stimulus program and took all that money out of wealthy people," he said. "What do wealthy people do with their money? They invest it, spend it, save it or give it away. And I guarantee you, any wealthy person who created that value is going to do far better doing those four things than taxing it and giving it to Pelosi and Reid and Obama."

Apparently he does not even understand that the stimulus was paid for by borrowing, not taxing. Among many other things.

$288 billion of the stimulus was tax cuts.

The wealthy invested in the stimulus by purchasing the bonds issued by the U.S. Government, which they now wish to default on.

The Republican Party is a city of stupid people on a hill made of sh*t.

Cite: http://useconomy.about.com/od/candidatesandtheeconomy/a/Obama_Stimulus.htm

The comments to this entry are closed.

Blog powered by Typepad