Phoenix Ignited is a proud tech solutions partner of Luxauro.com. View their news and media page here: Luxauro.com
Phoenix Ignited is a proud tech solutions partner of Luxauro.com. View their news and media page here: Luxauro.com
The Binary Search Algorithm takes a set of pre-organized data, such as an array of numbers like {1, 2, 3, 4, 5, 6, 11, 13, 199, 201,} and divides the set by two, then takes the middle number and compares it to the target number, if the middle number is the target number then the search is complete, but most likely it won’t be at first, in which case the algorithm determines if the target number is less than or greater than the middle number. If it is less than, then the middle number and every number in the array greater than the middle number is eliminated and the algorithm takes the middle number of the rest of the data set and repeats this process until it finds the target number. Now let’s get technical and actually explore what this algorithm is doing / how this algorithm is working in-depth.
You can find a general python binary search algorithm here on github: https://github.com/msambol/dsa/blob/master/search/binary_search.py It is the algorithm I will be referencing throughout this technical analysis. Also see this video here which can greatly help visualize and understand how this algorithm is working: https://www.youtube.com/watch?v=fDKIpRe8GW4
Now for our code that we will analyze:
def binary_search(array, target):
left = 0
right = len(array) - 1
while (left <= right):
mid = (right + left) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def main():
array = [1, 4, 5, 7, 9, 12, 15, 18, 19, 22, 25, 29, 40, 50]
print(f'Index of 12: {binary_search(array, 12)}')
print(f'Index of 1: {binary_search(array, 1)}')
print(f'Index of 9: {binary_search(array, 9)}')
print(f'Index of 22: {binary_search(array, 22)}')
print(f'Index of 50: {binary_search(array, 50)}')
print(f'Index of -1: {binary_search(array, -1)}')
main()
We can see that this algorithm declares a function called binary_search and that this function takes two parameters / arguments the array (data set) and the target value ( the value we want to find within the data set) such as 12 or 23 etc.
Next we see that the algorithm declares two indices, left and right. It assigns the left index to 0 and the right to the length of the array -1.
NOTE: We assign the right index to the length of the array -1 due to the following reason: Assume a number line of points 1, 2, and 3. Now in programming we often assign the first place the index 0 (we start from 0 not 1), so let’s label the left index 0 now if we label the right index 3 (after all there are three numbers in our data set) when we count from point 0 to 3 we would get 4 which would be the total number of numbers on the number line, BUT there are only three (3) not 4 numbers on the number line. Thus we mark the right index as 3.
NOTE: The Index is not the same as the value of the data point. The index refers to the point’s relation to other data points. Take a string of numbers 1, 32, 35, 94, 97, the first data point has an index of 0 and the last data point has an index of 4.
Next we have a while loop that specifies that so along as the left index is less than or equal to the right index do the following:
It loops the loop now until it finds the index of the target value. If it searches the entire data set without finding the target value it then returns -1.
Finally at the end there is a main function that runs a set of values through the algorithm to display how it works.
Walter Miely is a tech entrepreneur and CEO of Phoenix Ignited Tech You can find him on Linkedin. This material is licensed under the CC BY 4.0 License LEGAL DISCLAIMER: The content provided here is provided AS IS, and part of, or the entirety of this content may be incorrect. Please read the entireLegal Disclaimer here.
+ Ave Maria +
