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 2020-10-04: Added link to Bisection Search Calculator Spreadsheet

Older updates are archived at the bottom under the Updates section.

Tips Before You Start

• Start from a set of baseline parameters or at least default parameters
  • Otherwise you’ll have no stable comparison to decide if the final results are an improvement.
• Determine the order of parameters to search to minimize parameters that may be affected by tuning of later parameters
  • Otherwise you’ll find you realize you need to go back to earlier searched parameters and re-search them which is tedious and frustrating. You’ll want to eliminate or minimize this.
• Search one parameter at a time
  • Otherwise you’ll have difficulty picking out the change in feeling when trying the new value. This is especially true as precision increases and the change between the old and new values is very small and only produces a subtle difference in feeling.
  • But! Some parameters may feel better when adjusted by the same amounts together (probably because they affect each other in additive or subtractive ways). First, bisection search these together and, if they converge on the same value, and you feel confident they complement each other, start adjusting them together with the same value increments/decrements.
• Know when to stop
  • Otherwise you can go forever. Literally. It’s math. You can keep dividing something in half forever so far as we know. If there’s a precision limit on the parameter then try to feel your way to that precision limit, if possible, otherwise stop when you’re absolutely unsure whether a change if better or worses

Tips For Searching

• Always search minimums and maximums even if you started at a value somewhere in the middle
  • Otherwise you won’t get a feel for the range of values and you won’t have an adequate picture to inform your choice of whether you should increase or decrease the value.
• Always use new values exactly half-way between previous and current values
  • Otherwise you’re not doing bisection searching and you’re losing the value of bisection searches which iteratively narrows down a parameter to its optimal value.
• When you’re unsure to increase or decrease:
  • If unsure of whether to increase or decrease, put in more time to see if you can start to pickup the differences. Sometimes, especially with very subtle adjustments, it can take more time to feel the differences.
    • Otherwise you’re guessing and guessing defeats the purpose of a bisection search (ie. finding optimal value based on specific criteria). Try your best to figure out which you prefer.
  • If still unsure of whether to increase or decrease, try an experiment comparing an increase vs the current value and an decrease vs the current value.
    • Otherwise you’re guessing and guessing defeats the purpose of a bisection search (ie. finding optimal value based on specific criteria). Try your best to figure out which you prefer.
    • It is important, when running an increase/decrease experiment, to compare against the current value again so that you’re not simply deciding on whether you like Increase more than Decrease, or vice versa, but you’re deciding that you like Increase vs Current more than Decrease vs Current. So, run an experiment like this:
      • Test Current: Unsure
      • Test Decrease: Rank Better or Worse than Current
      • Test Current to get a feel for the value again
      • Test Increase: Rank Better or Worse than Current
      • Choose the Better value
      • If both are Better than Current then now compare them directly
  • If still unsure, consider whether the current value is “good enough.”
    • Otherwise you’re guessing and guessing defeats the purpose of a bisection search (ie. finding optimal value based on specific criteria). Try your best to figure out which you prefer.
    • You can try smaller adjustments but this may also lead to false positive results. Really, really try to feel out the differences.

Bisection Hacks

The hacks, or shortcuts, are techniques I’ve used to avoid having to bisection search the whole range over and over again.

• Round Bisection Values to Avoid Missing Steps
  • When dealing with limited precision, round up or down to the given precision, so that you’re not missing out on certain values.
  • For example, say you’re bisection searching a sequence of integers from 1 to 10. You proceed with 1, 10, 5, and want to go up but should it be by +2 or +3 because +2.5 wouldn’t result in a valid value. Round up when increase and round off when decreasing. So, in the example, it would be 1, 10, 5, 8 (2.5 -> 3), 6 (1.5 -> 2), 7 (0.75 -> 1).
  • This technique helps you avoid missing out on values due to limited precision. If you don’t do this, you might end up with a sequence like 1, 10, 5, 7, 6 and you’d miss the last value because there’s no where to go.
• Backwards Bisection Searching to Avoid Complete Re-searches
  • Once you’ve completed a full round of bisection searching and realize, maybe after further experimentation, that it needs to be changed slightly, don’t bisection search all over again: Instead, start backwards, meaning add a small value, then, instead of halving it you double it, and keep doubling it until you don’t like it, and then you start a regular bisection search by having the difference.
  • For example, say you’ve landed on 83 in a range of 1-100 but now you want to adjust it. You know you want a little higher value so adjust it by +1, then +2, then +4, and so on, until you no longer want to increase, then you start a regular bisection search within the 83-N range.
    • The amount you start adjusting by will vary on the scenario. In a range of 1-100 +1 might be appropriate. In a range of 0-1 then 0.01 might be appropriate.
  • This technique helps avoid redoing complete bisection searches by narrowing the range you need to search to the current value plus some small adjustments.

Bisection Search Calculator Spreadsheet

Click here to for an online Bisection search Calculation Spreadsheet that I use that provides predefined, helpful calculations already setup for you.

 

Case Study: Tuning Force Feedback Parameters in GTR2 – FIA GT Racing Game

This post came about because I found myself doing an incredible amount of bisection searching of force feedback parameters for my racing wheel for the racing simulation GTR2. You can read about my force feedback searching, including bisection search results, in my post Secrets of GTR2.

This is a real life example of where bisection searching becomes necessary to tune in values to achieve optimal results: In my case, for optimal force feedback in my racing wheel. Without finding the proper values, racing was not as enjoyable and not as informative as it really needs to be due to the age of game.

Credits

• Feature Image (NJIT.EDUT CS435)

Updates