How to Perform Binary Search in Python: Tips and Best Practices

What is a binary search?

A binary search is an algorithm for searching for a specific value in a sorted array or list. It works by repeatedly dividing the search range in half until the target value is found or determined to be not present in the array.

Here’s how a binary search algorithm typically works:

1. Calculate the middle index (l+r)//2 of the array.
2. Compare the middle element of the array with the target value.
3. If the middle element is equal to the target value, the search is complete and the index of the element is returned.
4. If the middle element is greater than the target value, search the left half of the array by updating the high index to be one less than the current middle index.
5. If the middle element is less than the target value, search the right half of the array by updating the low index to be one more than the current middle index.
6. Repeat steps 1-5 until the target value is found or the search range is empty (i.e., the low index is greater than the high index).

A binary search is an algorithm for searching for a specific value in a sorted array or list. It works by repeatedly dividing the search range in half until the target value is found or determined to be not present in the array.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This is because, with each comparison, the search range is reduced by half. This makes the binary search very efficient for large arrays compared to linear search algorithms that have a time complexity of O(n).

Why do we need to learn binary search (BS)?

A binary search algorithm can be useful in many business cases where the data set is sorted and the application needs to search for specific values efficiently. Here are some examples:

1. Database search: Binary search can be used to search a sorted database for specific records, which can improve the efficiency of the search process.
2. E-commerce: When a user searches for a product on an e-commerce website, the website needs to search its database to find the relevant products. If the database is sorted by product name or price, a binary search can quickly find the products matching the search criteria.
3. Stock market analysis: In stock market analysis, traders may need to search for specific stock prices or perform analysis on a range of prices. A binary search can be used to quickly locate the relevant data.
4. Online gaming: In online gaming, the game server may need to search for specific player data, such as high scores or rankings. A binary search can help to quickly locate this data in a large database of player records.

In general, any application that requires searching or sorting large data sets can benefit from implementing a binary search algorithm to improve efficiency and reduce search time.

Implementation Template

So, there are two ways to implement binary search in python.

1. Built-in API

Python has a built-in binary search API, which can be implemented in the following example:

import bisect

# Sorted list of integers
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Target value to search for
target = 7

# Find the index where the target value should be inserted in the list
index = bisect.bisect(nums, target)

# Check if the target value is in the list at the found index
if index != len(nums) and nums[index] == target:
    print("Target value found at index:", index)
else:
    print("Target value not found")

2. Implement a basic binary search algorithm

def binary_search(arr, x):
    # Set initial low and high indices
    low = 0
    high = len(arr) - 1
    
    # Loop until low index is less than or equal to high index
    while low <= high:
        # Calculate mid index
        mid = (low + high) // 2
        
        # If x is found at mid index, return mid
        if arr[mid] == x:
            return mid
        
        # If x is less than the value at mid index, search the left half of the array
        elif arr[mid] > x:
            high = mid - 1
        
        # If x is greater than the value at mid index, search the right half of the array
        else:
            low = mid + 1
    
    # If x is not found, return -1
    return -1

Quick practice:

There are a few interesting practices in LeetCode Problem Challenges. I am going to share there easy binary search problems that I have completed. The links are attached below:

https://leetcode.com/problems/binary-search/

https://leetcode.com/problems/search-insert-position/

https://leetcode.com/problems/first-bad-version/

If you feel this post has been helpful to you in algorithm learning, please comment below any of your thinking and share the post with people who are struggling with learning binary search. Thank you.

🙂 Peace