Recursive binary search in Python

Question

I am trying to understand this function with little to no avail. I completely understand what a binary search is but am only new to the concept of recursion but do have a slight grasp on it. I don't really understand what the default values of low and high would be when first calling the function. As of right now I am just including the search space I know the number is in, but what if I don't or I am not sure of the list length? Otherwise, I understand the recursion process going on here as well as the need for low and high being arguments. The function below is provided in the notes by an online course I am taking; however, it wasn't explained in the lecture and contains no docstrings or references about it.

def bSearch(L, e, low, high):
 if high - low < 2:
 return L[low] == e or L[high] == e
 mid = low + int((high-low)/2)
 if L[mid] == e:
 return True
 if L[mid] > e:
 return bSearch(L, e, low, mid-1)
 else:
 return bSearch(L, e, mid+1, high)
L = [1,3,6,15,34,84,78,256]
print bSearch(L, 15, 4, 8)
print bSearch(L, 84, 0, 6)

Output:

False
True

Answer 1

High and low appear to be indices for which part of the list to search.

In the first example, 15 has an index of 3, so specifying a lower index of 4 means the 15 isn't included in the search space. In the second example, 84 has an index of 5, so it is included in the search space spanning indices 0 and 6.

These indices are also inclusive. If the second example were:

print bSearch(L, 84, 0, 5)

the answer would be:

True

If you want to search the entire list, you can simply do:

print bSearch(L, 84, 0, len(L) - 1)

where the - 1 is necessary because the search function is inclusive.

• Jordan: Thank you, I figured this out by running tests but my more direct questions is what if I didn't know where in the list the value was or even the size of the list? Is that just a limit to this function or am I missing a key concept?
• huu: You don't have to know where in the list the value is if you search the entire space. The size of the list is easily available in len(L). I've edited my answer to include this type of search.
• Jordan: Oh, thank you very much! That is what I was looking for. I knew it was possible but I guess I was just drawing a blank. Also, it would probably be way more useful to return the index rather than just a true or false in most cases, correct?

Answer 2

Binary search .

bsearch(list , element to be found , start index , end index). start index can be taken as 0 at the start of the function and last index can be taken as len(list)-1

As in question for bsearch(L,15 , 4 , 8 ). U are searching only between 5th and 9th element where the number is not present.

In the second function call u are searching between first element and 5 th element where a number present.

U can call this function as bsearch(L , 15 ,0 , len(L) - 1) for any other number.

Hope this helps.

Answer 3

low and high specify the indices of L where the algorithm must search. In the first example, 15 has the index 3. This is not in the interval [4,8] so it will return false. In the second example the index of 84 in L is 5, this is in the interval [0,6] so this will return True.

If the number you are searching for is not in L this method will return False. Why? Because you end up in the base case of if (high-low) < 2. In this case there will be checked against L[high] or L[low] being equal to the number you are searching for. If both are not the case, it returns False. This is the definition of the logical or.

False or False = False False or True = True True or False = True True or True = True

If you are not sure about the list length, this will produce an error if the high or low value you provide are not in the range of L. You can add an extra condition so this can not happen, but I think that is out of the scope of that lesson. :)