Bisection Search Like A (Human) Boss

Bisection search, or binary search for us developers, is a technique for finding the best value within a given range of values. This post describes tips for when you need to bisection search manually by hand (by “feel”), as opposed to when it can be automated by, say, a computer algorithm.

Bisection search, or binary search for us developers, is a technique for finding the best value within a given range of values.  Technically speaking, Wikipedia says the “bisection method in mathematics is a root-finding method that repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing.” This post describes tips for when you need to bisection search manually by hand (by “feel”), as opposed to when it can be automated by, say, a computer algorithm.

For example, say you’re very thirsty and need water fast so you pour yourself a glass of water: Pour too fast and it spills but too slow and it takes too long. You want to pour fast enough to quench your thirst as soon as possible but not so fast that it spills. The speed of pouring is your range of values (eg. slow to fast) and the consequences of the speed of pouring (how long it takes and if it spills) are your criteria to decide the best value. You try pouring the glass slowly and it’s too slow: Pour faster. You try pouring the glass faster and it spills: Pour slower but faster than the first time. You try pouring the glass “just right”: It’s fast enough and doesn’t spill. You’ve found the best pouring speed by bisection search!

Update 2017-10-26: Added sections: Bisection Hacks, and Case Study: Tuning Force Feedback Parameters in GTR2 – FIA GT Racing Game.

Continue reading “Bisection Search Like A (Human) Boss”