cropped-phoenixignitedlogo1.png

Binary Search Algorithm

Binary Search Algorithm

  • July 18, 2024

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.

In-Depth Analysis

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: 

  • Declare a middle index which equals the left plus the right index and divides the output by two, the result is the index of the middle number. (Think 0 + 2 = 2 / 2 = 1 thus the midpoint on a number line of 1, 2, 3 would be 2 which holds an index of 1 on the number line, we started at 0, so index 1 would be the number 2).
  • If the middle point of the array happens to be the target number then the algorithm returns the middle index.
  • Else if the value of the middle index of the array is less than the target value than the algorithm resets the left index to the middle index plus 1 (so if our target value on our number line of 1, 2, 3, was 3 then the algorithm would check the value of the middle index which is 2 against the target value (which is 3) and if the value of the middle index is less than the target value (which 2 < 3) then it would reset the left index to the middle index plus 1, so because 2 < 3 then 1 < 3 also so now the left index becomes 2 which the value of the index 2 is 3).
  • Otherwise if the middle index is not less than the target value , it moves the right index to the middle index -1. Basically because the algorithm already determined that the value of the middle index does not equal the target value, and that the value of the middle index is not less than the target value than the middle index must in fact be greater than the target value and therefore moves the right index to the middle and subtracts one or one to the left of the middle index.

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.

IONOS - Official Partner
Github Codepen Linkedin X-twitter Flickr Medium

+ Ave Maria +