Binary Search using Python

Binary Search is an algorithm used to find an element in a sorted array by repeatedly dividing the search interval in half. In coding interviews, there is always a question on any search algorithm. So, if you want to learn how to use the binary search algorithm, this article is for you. In this article, I will take you through an implementation of the Binary Search algorithm using Python.

Binary Search Algorithm

The binary search algorithm is a searching algorithm used to find an element in a sorted array by repeatedly dividing the search interval in half. Below is how the Binary Search algorithm works:

1. It starts by defining a search range that spans the entire array.
2. Then compares the target value with the middle element of the search range.
3. If the target value is equal to the middle element, the target is found and returns its index.
4. If the target value is less than the middle element, the algorithm discards the upper half of the search range and repeats step 2 with the lower half.
5. If the target value is greater than the middle element, the algorithm discards the lower half of the search range and repeats step 2 with the upper half.
6. It repeats steps 2 through 5 until the target value is found or the search range is empty.

Below is the kind of input and output you will see in the problem of binary search in your coding interviews:

• Input = [-1,0,3,5,9,12], target = 9 | Output = 4

Binary Search using Python

I hope you have understood the Binary Search algorithm and how it works. Below is how you can implement it using Python to solve problems based on searching:

def search(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [-1,0,3,5,9,12]
target = 9

print(search(nums, target))

Output: 4

Below is how the above code works:

1. We start with two variables low and high that define the search range as the entire array;
2. We use a while loop to repeatedly halve the search interval until the target element is found or the search interval is empty;
3. At each iteration of the loop, the index of the element in the middle of the search interval is calculated using the formula (low + high) // 2;
4. We compare the target value with the middle element of the search range:
   • If the target value is equal to the middle element, we have found our target and can return its index;
   • If the target value is less than the middle element, we discard the upper half of the search range and repeat the process with the lower half;
   • If the target value is greater than the middle element, we discard the lower half of the search range and repeat the process with the upper half;
5. If the target element is not found after all iterations of the loop, we return a “not found” signal, which in this case is -1.

So this is how you can implement the binary search algorithm using Python. You can find many more practice questions for coding interviews solved and explained using Python here.

Summary

The binary search algorithm is a searching algorithm used to find an element in a sorted array by repeatedly dividing the search interval in half. I hope you liked this article on implementing the Binary Search algorithm using Python. Feel free to ask valuable questions in the comments section below.