Using Lua to do a Binary Search

This is a quick exercise I did with Sam my finance manager:

This is the Lua code which implements a binary search:

function BINsearch(TargetFunc, Low, High)
   local Range = High - Low
   local Threshold = 1
   trace(Range)
   local LowValue = math.abs(TargetFunc(Low + Range/3))
   local HighValue = math.abs(TargetFunc(High - Range/3))
   if (LowValue <= HighValue) then
      if (LowValue < Threshold) then
         return Low + Range/3
      end
      return BINsearch(TargetFunc, Low, Low + Range*2/3)
   else
      if (HighValue < Threshold) then
         return High - Range/3
      end
      return BINsearch(TargetFunc, Low+Range/3, High)    
   end
end

And here is some example code to show it’s usage:

require 'BINsearch'

function APPtarget(Input)
   return Input-20000
end

-- The main function is the first function called from Iguana.
function main()
   local HighGuess = 19000
   local LowGuess = 0
   local Result = BINsearch(APPtarget, LowGuess, HighGuess)   
   APPtarget(Result)
end

You might want to checkout the related concept of doing this in Microsoft Excel using the solver addin.

Concepts

Using Lua to do a Binary Search

Analytics

Related content