Your first one won't even get started, because list(mid)
will immediately raise a TypeError: 'list' object is not callable
.
If you fix that (by using list[mid]
), your next problem is that you ignore the min
and max
arguments you receive, and instead set them to 0
and len(list)-1
each time. So, you will infinitely recurse (until you eventually get a RecursionError
for hitting the stack limit).
Think about it: the first call to binarySearch(l, 5, 0, 10)
recursively calls binarySearch(l, 5, 0, 4)
. But that call ignores that 4
and acts as if you'd passed 10
, so it recursively calls binarySearch(l, 5, 0, 4)
. Which calls binarySearch(l, 5, 0, 4)
. And so on.
If you fix that (by removing those two lines), you've got another problem. When you give it the number 10
, binarySearch(l, 10, 0, 10)
will call binarySearch(
l, 10, 6, 10), which will call
binarySearch(l, 10, 8, 10)
, then binarySearch(
l, 10, 9, 10), then
binarySearch(l, 10, 10, 10)
. And that last one will check list[10] > element
. But list[10]
is going to raise an IndexError
, because there aren't 11 elements in the list.
And once you fix that off-by-one error, there are no problems left. The problem you asked about cannot possibly ever occur. Here's an example run:
>>> a = range(10)
>>> for i in -3, -1, 0, 1, 4, 5, 9, 10, 11:
... print i, binarySearch(a, i, 0, 10)
-3 False
-1 False
0 0
1 1
4 4
5 5
9 9
10 False
11 False
Your second version isn't recursive. bSearch
never calls bSearch
, and that's the whole definition of recursion.
There's nothing wrong with writing an iterative algorithm instead of a recursive algorithm (unless you're doing a homework problem and recursion is the whole point), but your function isn't iterative either—there are no loops anywhere.
(This version also ignores the start
and end
arguments, but that's not as much of a problem in this case, because, again, you're not doing any recursion.)
Anyway, the only return False
in the function is in that first if len(list) == 0
. So, for any non-empty list, it's either going to return True
, or a number. With your input, it will return 4
for anything less than the value at the midpoint of the list (5), and True
for anything else.