DEV Community

Cover image for Binary search algorithm
Damian Brdej
Damian Brdej

Posted on

5 1

Binary search algorithm

Binary search is an algorithm in which a sorted list of elements is given as input. If the list contains the item we are looking for, the algorithm returns information about its location. Otherwise, it returns the null value.

In a binary search, we guess the middle number in order to eliminate half of the remaining numbers in each trial.

def binnary_search(list, item):
    low = 0
    high = len(list) - 1  #1

    while low <= high:
        mid = round(low + high) // 2    #2
        guess = list[mid]

        if guess == item:     #3
            return mid
        if guess > item:      #4
            high = mid - 1
        else:                 #5
            low = mid + 1
    return None

my_list = [1, 2, 3, 5, 7, 9, 11, 23, 123, 345]

print(binnary_search(my_list, 345)) #9
print(binnary_search(my_list, 11)) #6
print(binnary_search(my_list, 15)) #None
Enter fullscreen mode Exit fullscreen mode

Let's break this program down into parts:

  1. Use low and high to control which part of the list is searched

  2. As long as the search area has not been narrowed down to one element, we select the middle element

  3. Element found

  4. Our guess is too big

  5. Our guess is too low

  6. There is no such element

Remember that numbering in lists starts at 0

Binary search is a good alternative to searching the entire list of items one by one. The speed of a binary search with a list of 10 elements is O(log 10) which gives us a maximum of 4 guesses.

More about Big O notation you can read in my previous post here

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

Retry later