Binary Search Algorithm in Python

Practice Java programming from home without using any fancy software just by tapping on this Simple Java Programs for Beginners tutorial.

Binary Search:

A binary search is an algorithm for finding a specific element in a list. Assume we have a list of a thousand elements and we need to find the index location of a specific element. Using the binary search algorithm, we can quickly determine the index location of an element.

There are several search algorithms, but the binary search is the most widely used.

To use the binary search algorithm, the elements in the list must be sorted. If the elements are not already sorted, sort them first.

Examples:

Input:

given_elements =[2, 7, 3, 4, 9, 15]   key= 9

Output:

Element 9 is found at index 4

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

1)Algorithm

We write a function that takes two arguments, the first of which is of which is the list and the second of which is the objective to be found.
We declare two variables start and end, which point to the list’s start (0) and end (length – 1), respectively.
Since the algorithm would not accept items outside of this range, these two variables are responsible for removing items from the quest.
The next loop will continue to locate and delete items as long as the start is less than or equal to the end, since the only time the start exceeds the end is if the item is not on the list.
We find the integer value of the mean of start and end within the loop and use it as the list’s middle object.

2)Implementation

Below is the implementation of linear search:

# function which return index if element is present else return -1
def binarySearch(given_list, key):
    lowindex = 0
    highindex = len(given_list) - 1
    midindex = 0
    # loop till lowindex is less than or equal to highindex
    while lowindex <= highindex:
       # Modify midindex with average of high index and lowindex
        midindex = (highindex + lowindex) // 2

        # If key is greater than mid element ignore left half side of list
        if given_list[midindex] < key:
            lowindex = midindex + 1

        # If key is less than mid element ignore right half side of list
        elif given_list[midindex] > key:
            highindex = midindex - 1

        # Else the element is present at mid index
        else:
            return midindex

    # if any value is not returned then element is not present in list
    return -1


# given_list
given_list = [2, 7, 3, 4, 9, 15]
# given key
key = 9
# sort the list
given_list.sort()
# passing the given_list and key to binarySearch function
res = binarySearch(given_list, key)
# if result is equal to -1 then element is not present in list
if(res == -1):
    print("Given element(key) is not found in list")
else:
    print("Element", key, "is found at index", res)

Output:

Element 9 is found at index 4

3)Time Complexity

Consider a basic searching algorithm such as linear search, in which we must go through each element one by one before we find what we’re looking for. This means that for larger input sizes, the time it takes to find an element grows in lockstep with the input size. Its time complexity is O measurably (n).

The term “time complexity” refers to the measurement of how quick or efficient an algorithm is. The time complexity of Binary Search is “O(log2n),” which means that if we double the size of the input list, the algorithm can only perform one additional iteration.

In the same way, if the input size is multiplied by a thousand, the loop would only need to run 10 times more.

Remember that half of the list is removed with each iteration, so eliminating the entire list won’t take long.
Related Programs: