In the previous post, the binary search in python was discussed but not in enough detail. Therefore, in this post, the binary search in python shall be discussed in depth.
Introduction
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 involves checking if the middle element of the array is the element 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 array. This is dome until we find the intended element.
NOTE: The list to be searched must be sorted.
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.
You can check out other posts below:
Sorting and Searching in Python
Download chrome driver using Selenium
Guess the number game in Python
