Binary Search in Python

Binary Search in Python

Binary search in python involves looking for a specific element in a list or an array. It is referred to as a binary search because it consists in checking if the middle element of the array is the part being looked for. If not, then the list is split into two. We will take one of the new subarrays created as an array and do to it what we previously did to the original collection. This is dome until we find the intended element.

Recursive Binary Search in Python

In this method, some key concepts need to be understood.

First, the length of the array will keep changing, and to keep track of this, we use the beginning point of the respective array. This simply means that whenever we have an array, we take the middle position with respect to the beginning value and the length of the array. When we split an array to get a subarray, we get a new beginning position and a new middle position.

The function we are going to define will take four parameters. The first the list that acts as a dictionary to Binary Search from. The second and the third are the beginning position and the length of the array in question. These two will be used to get the middle value. The algorithm will involve function recalling hence we cannot hardcode these two since they need to be dynamic. If we hard code them, every time we recall the function, their values will be the same and we will get the same middle value making the function be stuck in a never-ending loop.

With all this key information, let us now look at the first Binary Search in Python algorithm.

# Method one

def binarySearch (values, l, r, element):

# l is the starting reference to find the middle.

# It will keep changing time we split the array to get subarrays.

# Hence it is not hard coded into the algorithm.

# It won't make much importance to the user since the user needs to know the first middle point is in reference with the first index which is zero.

# Therefore when calling the function, l will be 0.

# R is the lenght of the list.

# Python's len() function gives the accurate lenght but indexing starts at one value less.

# Hence the lenght will be one value less.

# Check if the list has not been exhausted.

if r >= l:

# We are checking i

mid = l + (r - l) // 2

# We start at the middle of the list and check if the element

if values[mid] == element:

return "Element " + str(element) + " is at " + str(mid + 1)

# We check if the element is on the left side of the split array

elif values[mid] > element:

return binarySearch(values, l, mid-1, element)

# Otherwise, the element is in the right side of the split array.

else:

return binarySearch(values, mid + 1, r, element)

# If we fail to find the element in the list we return an absent statement.

else:

# Element is not present in the array

return "Element " + str(element) + " is not in the list"

Loop Binary Search in Python

This method is a little simpler as compared to the first one but is quite complex in its calculation.

Unlike the previous Binary Search, we do not have any recursive function. This means we do not recall the function and hence we can hard code some values.

In place of the recursive function, we implement a loop that will increment these values. A while loop is used since we are not iterating over the list. If we were iterating over the list then the binary search will change to a linear search since we are not splitting the list as well.

The while loop will run as long as the subarrays have not been exhausted. Let us look at the second Binary Search in Python algorithm

def binarySearch2(values, element):

# The function takes two parameters.

# Values is the list that acts as a dictionary to search the element from.

# The element is the value being searched for.

start = 0

# This is the beginning value of the array in question.

# The value will change depending on the array.

length = len(values)-1

# This is the length of the array in question.

# This number will vary on whether the list is split or not.

while start <= length and element >= values[start] and element <=values[length]:

#This means that the search loop will run as long as these three conditions are met.

# The first is as long as the list has not been exhausted. As long as the start is smaller than or equal to the lenght

# The second is that the element is larger than the start value on the list.

# The last one is that the element is smaller than the last element on the list.

# Find the middle point.

mid = start + int(((float(length-start)/(values[length]-values[start]))*(element-values[start])))

# This calculation simply adds the previous mid to an incremented value.

# Compare the middle value on the list to the element being searched for.

if values[mid] == element:

# If we find the element, we print out its value position on the list.

return "Element " + str(element) + " is at " + str(mid + 1)

if values[mid] < element:

#If we fail to get the element in this current loop, we increment and move to the next loop.

start = mid + 1

#If we fail to get the number completely, we print out an absent statement.

return "Element " + str(element) + " has not been found."

Thank you for reading through my post. Please leave a comment or any query below.

Let’s be friends! Follow me on Twitter and FaceBook and connect with me on LinkedIn. You can visit My website Too . Don’t forget to follow me here on Medium as well for more technophile content.