The bisection algorithm



It's based on the idea of finding a desired element from a sorted arrangement of values by discarding half the information every time.
One of the best ways to exemplify the bisection algorithm is by finding the square root of a number


The parameters for the algorithm are:

  • TARGET: float - the target value whose square root we try to find. Always positive
  • MIN: float - the minimum value below which the square root of a TARGET cannot be found
  • MAX: float - the maximum value over which the square root of a TARGET cannot be found
  • CANDIDATE: float - a candidate value to determine its proximity to the square root of the target when raised to the square
    • # DATA DEFINITIONS

TARGET = 25 #The value whose square root we're trying to find

# DD. MIN
# min = float
# interp. the minimum value below which the square root of a TARGET cannot be found
min = 0

# DD. MAX
# mac = float
# interp. the maximum value over which the square root of a TARGET cannot be found
max = TARGET

# DD. CANDIDATE
# candidate = float
# interp. a candidate value to determine its proximity to the square root of the target when raised to the square
candidate = min + ((max-min)/2)

    The Algorithm

  • While the absolute value, of the difference between CANDIDATE^2-TARGET, is bigger than a threshold (e.g. 0.00001):
    • Here is a video that hopefully helps with clarification!
    Let's work through the implementation together! 
    # DATA DEFINITIONS

TARGET = 25 #The value whose square root we're trying to find

# DD. MIN
# min = float
# interp. the minimum value below which the square root of a TARGET cannot be found
min = 0

# DD. MAX
# mac = float
# interp. the maximum value over which the square root of a TARGET cannot be found
max = TARGET

# DD. CANDIDATE
# candidate = float
# interp. a candidate value to determine its proximity to the square root of the target when raised to the square
candidate = min + ((max-min)/2)



# CODE

while abs(candidate**2 - TARGET) > 0.000001:
    candidate = min + ((max-min)/2)
    if candidate**2 > TARGET:
        max = candidate
    elif candidate**2 < TARGET:
        min = candidate
    else:
        break

print(candidate)