DEV Community

martin_ndegwa
martin_ndegwa

Posted on

Binary Search Algorithm

What is binary search algorithm?
Well, it's an algorithm :)
An algorithm is a set of finite instructions or rules used to solve a particular problem. A binary search algorithm takes a sorted input of a list of elements, such as numbers. When the element you are searching for is in the list, the algorithm returns where it is located.

Why use Binary Search?
Binary search is well suited for a large input of elements.It is more efficient than a linear search where a case of say 1024 elements would take 1023 steps (worst case) or so to get an element near the 1024 mark. A binary search would take log n time to get an element from the same(worst case). log 1024 = 10 this means it would take 10 steps since 2 to the power of 10 is 1024. Simply log n here means logarithmic time and it's computed as log n to the base of 2 in layman's terms think of it as "How many 2s do we multiply together to get 1024?"
The time is shortened quite impressively right?

Now let's see how it works
The code here is in Python, but the logic is the same for other programming languages. Okay, so binary search works only with a sorted list and you'll keep track of the part of the list to search through, at first it's the entire array:

low = 0
high = len(list) - 1
Enter fullscreen mode Exit fullscreen mode

Each time you check the middle element;

mid = (low + high) / 2
guess = list[mid]
Enter fullscreen mode Exit fullscreen mode

Here your guess is that just maybe the element you are searching for is in the middle of your list, if the guess is too low, you'll adjust low accordingly:

low = mid + 1
Enter fullscreen mode Exit fullscreen mode

And if the guess is to high, you update high; Here is the full python code

"""binary search"""
def binary_search(list: [int], num: int) -> int:
    """num is the searched number in the list"""
    low = 0
    high = len(list) - 1
    list.sort() # sort the list


    while(low <= high):
        # get the middle element
        mid = (low + high) // 2
        guess = list[mid]

        if guess == num:
            return mid
        if guess > num:
            high = mid - 1
        else:
            low = mid + 1
    return 0

if __name__ == '__main__':
    number_to_search = 5
    list = [1,8,9,3,4,6,5,10,7]
    print(binary_search(list, number_to_search))
Enter fullscreen mode Exit fullscreen mode

The code returns 3 which is the position of 5 in the 0-based index of the sorted list.
You can try out the code with larger inputs and see the beauty of it. Alright that's it, Happy Coding!

Top comments (0)