THE PROBLEM
Stay with me on this one, I think it's a concept that every techie should understand and use at some point in their careers.
The problem goes like this: There's one program somewhere on your machine that's conflicting with another and causing CPU spikes and bringing the computer to a standstill, but you don't know which one. The problem is, you have 150 items in your Add/Remove Programs and you've been tasked with finding out which one is the problem.
Now, many people would say, "Well, I guess I just gotta start uninstalling them one at a time, reboot and see when the problem goes away...when it does, that program was the culprit." I've even done that myself. But I started thinking about some programming concept that would help me find the 1 program out of 150 in at most 7 tries.
THE SOLUTION
The machines I had to work with recently on this kind of a problem are old and slow (they're specific line of business machines running <barf> Windows 2000). So I didn't want to be constantly rebooting this nasty slow beast 150 times, or reimaging it too often, so I took a little time and thought about the best way to do this in as little work as possible. What came to me was the concept of a binary search.
In programming, there's this concept of a binary search where if you have an ordered list, you can find a result the fastest by a divide-and-conquer method. If the thing you're looking for in a list of 100 items is in the 36th spot, but you don't know that, you first look in spot 50 and determine if it's higher or lower than that. If it's lower, you look in spot 25 and determine if it's lower or higher, etc. until you reach the item you're looking for. For fun, let's use some ASCII art to illustrate this:
1 ---------------- 50 ------------------- 100
^
First check the value right in the middle. The real answer is lower so we know we can exclude 50-100
1 -------------- 25 ----------------- 49
^
Second, check the median of what's left. The answer is higher so we know we can exclude 1-25
26 ---------- 38 ----------- 49
^
Again, check the median. The answer is lower so we know we can exclude 38-49
26 ------ 32 ------ 37
^
The median of what's left is 32. The real answer is higher so exclude 26-32
33 -- 35 -- 37
^
The median is 35. The real answer is higher so exclude 33-35
36 - 37
^
The "median" is 37. The real answer is lower, so we can exclude 37
36
^
So there, it takes at most 6 guesses to filter out the 99 other numbers to get the answer. The good news is, it's logrithmic so starting with a list of 150 items only adds at most 1 more guess.
Seems to me we can use this same kind of filtering to weed out all the working programs and be left with the one that's bad. But instead of doing a greater than/less than on the values, we just operate on half of the programs at once and see if the problem goes away.
So, the theory goes, you uninstall half of the programs (75 out of 150). If the problem still exists, the bad program is in the half that you didn't uninstall, if not, it's in the half you just uninstalled. So, now uninstall half of the programs that are left (37 of the 74 left). If the problem still exists, the bad program is in the half that's left, if not, it's in the half you just uninstalled. Now uninstall half of that (19 of the 36 left), etc...
The end result will be that instead of making as many as 150 uninstalls and reboots (or worse, reimages), you'll have to make at most 7.
SUMMARY
Well, that's all there is to it, when you're trying to find a bad program in a large list of programs, try dealing with half of those objects at the same time and continually cut down half of what's left until you find the answer. It should seriously cut down the amount of work you'll have to do.
Number2 (John Nelson)
MyITForum - Forum Posts
MyITForum - Blog
