A function's calls must be consistent with its implementation. The search()
helper function is organized to return -1 under some conditions. However,
nowhere do you capture the return value. That does not make sense. Functions
are either called for their side effects (e.g., modifying the value of the
non-local lookup) or they are called for their return value (in which case,
you'd better capture it).
Base cases should not check unchanging information. When should we bail out
of search()? Not when the list is empty: the list never changes size, so
emptiness should be checked before search() is ever called. Bailing out of a
recursion should be driven by something that is changed as the function is
being called -- namely, when start and end cross each other, or when we
actually find the target number.
Global variables are never the answer. You're using functions, which is
good. However, you are undermining their power by resorting to nonlocal. In
this case, you are using this mechanism to create the effect of a global
variable within the scope of the binary_search() function. In well over a
decade of Python programming, I can remember only one use of global or
nonlocal, and that was for unusual circumstances where I was operating under
the constraints of a legacy code base. They just aren't needed under regular
circumstances, and they have a wide range of negative effects on software.
What's the solution? Pass start and end as arguments to search(), and
compute lookup only inside in function, never outside. The benefit of the
latter is that you need to compute its value in only one spot, not multiple. If
you're ever working on a recursive implementation and find yourself computing the
same values both outside and inside the recursive function, that's often a sign
that you have not organized the recursive logic well.
Use convenience variables to aid readability. The search() function uses
arr[lookup] several times. A simple convenience variable can simplify
and lighten up the code, enhancing readability.
Select descriptive and thematic variable names. Although num is good in
telling us that we're dealing with a number, it's still pretty vague. Much
better is a term that conveys the concept of something that is being searched
for: target is one option. Similarly, lookup is not a terrible variable
name, but it's also vague in the sense that it doesn't clarify whether lookup
is an index or value from the list. A more helpful name would build on the
theme you've already established with start and end: options are
midpoint, middle, or even just mid. Finally, since this is a general
purpose function, it's not easy to pick a good name for the list of values. In
that context, arr is fine. But a better name can be had by drawing on a
convention often seen in functional programming, where an arbitrary value can
be represented by a variable like x and a collection of such values can be
represented by pluralizing the variable name to become xs. Such names are
effective because convey (a) our lack of knowledge about the details of the
thing behind the variable, and (b) the connection between the collection (xs)
and a value from it (x).
Algorithmic code needs testing. Donald Knuth was a genius on the topic of
algorithms, and yet even he appreciated the difficulty of implementing
simple algorithms when he wrote the following: "although the basic idea of
binary search is comparatively straightforward, the details can be surprisingly
tricky". The way to avoid pitfalls is to organize your code from the beginning
to support testing. The best way to do that is to learn how to use one of the
Python testing frameworks, but if you're just learning or want a practical,
quick-and-dirty approach when working on programming exercises like this, you
can mimic the approach taken in main() below: define a collection of test
cases (inputs and expected output); iterate over the collection; confirm that
the return value matches expectations.
def main():
tests = (
([], 99, -1),
([1, 2], 1, 0),
([1, 2, 4], 4, 2),
([1, 2, 3, 4], 4, 3),
([2, 4, 5, 99, 100], 5, 2),
(tuple(range(1, 1000)), 50, 49),
)
for xs, target, exp in tests:
got = binary_search(xs, target)
if got == exp:
print('ok', target)
else:
print('FAIL', target, exp)
def binary_search(xs, target):
def search(start, end):
mid = (end + start) // 2
x = xs[mid]
if x == target:
return mid
elif end <= start:
return -1
elif target > x:
return search(mid + 1, end)
else:
return search(start, mid - 1)
return search(0, len(xs) - 1) if xs else -1
if __name__ == '__main__':
main()
Why bother with recursion?. I would not use recursion for
a simple case like this: check for emptiness; initialize start and
end; and enter a while-true loop, modifying start and end inside
the loop rather than recursing. At a minimum, it's worth implementing
a non-recursive version to compare the two and see what you think.
