Binary Search in Python

Binary Search in Python

When working with large amounts of data, finding a specific element quickly is an important part of programming. Binary Search in Python provides an efficient way to locate an element by repeatedly dividing a sorted list into smaller sections.

Unlike Linear Search, which checks elements one by one, Binary Search reduces the search space by half after every comparison. This makes it much more efficient when working with large sorted datasets.

In this tutorial, we will understand the concept of Binary Search, learn how it works, and implement it in Python using both iterative and recursive methods.

Complete Advance AI Topics: Click Here
SQL Tutorial: Click Here

What is Binary Search?

Binary Search is a searching technique that follows the divide-and-conquer approach. It finds an element by repeatedly dividing a sorted list into two parts and checking which part can contain the required value.

For example, consider the following sorted list:

list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45

How Does Binary Search Work?

Binary Search uses two pointers:

• low: Represents the beginning of the current search range.
• high: Represents the end of the current search range.

The middle position is calculated using:

mid = (low + high) // 2

For the above list:

low = 0
high = 6

mid = (0 + 6) // 2
mid = 3

The value at index 3 is 39. Since 45 is greater than 39, we know that the required element must be in the right half.

The search continues by calculating a new middle position. When the middle element matches the target, its index is returned.

Steps of Binary Search

1. Make sure the list is sorted.
2. Set low to the first index.
3. Set high to the last index.
4. Calculate the middle index.
5. Compare the middle element with the target value.
6. If they are equal, return the middle index.
7. If the target is greater, search right half.
8. If the target is smaller, search left half.
9. Repeat until the element is found or the search range becomes empty.

Binary Search Algorithm

BinarySearch(list, key)

    low = first index
    high = last index

    while low <= high:
        mid = (low + high) // 2

        if list[mid] == key:
            return mid

        if key > list[mid]:
            low = mid + 1

        else:
            high = mid - 1

    return -1

Binary Search in Python Using Iterative Method

The iterative method uses a while loop to repeatedly reduce the search range.

# Iterative Binary Search in Python

def binary_search(list1, n):
    low = 0
    high = len(list1) - 1

    while low <= high:
        mid = (low + high) // 2

        if list1[mid] < n:
            low = mid + 1

        elif list1[mid] > n:
            high = mid - 1

        else:
            return mid

    return -1


# Example
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45

result = binary_search(list1, n)

if result != -1:
    print("Element is present at index", result)
else:
    print("Element is not present in list1")

Output

Element is present at index 4

Explanation

Recursive Binary Search in Python

• The binary_search() function accepts a sorted list and the target value as input.
• The low pointer starts at the first index, while high points to the last index.
• The middle index is calculated using integer division.
• middle element is smaller than target, continue the search in right half.
• middle element is greater than target, continue the search in left half.
• When the middle element matches the target, its index is returned.
• If no matching element is found and the search range becomes empty, the function returns -1.

Binary Search can also be implemented using recursion. In this approach, the function calls itself with an updated search range until the target is found or the range becomes invalid.

# Recursive Binary Search in Python

def binary_search_recursive(list1, low, high, n):

    if low <= high:
        mid = (low + high) // 2

        if list1[mid] == n:
            return mid

        elif list1[mid] > n:
            return binary_search_recursive(
                list1, low, mid - 1, n
            )

        else:
            return binary_search_recursive(
                list1, mid + 1, high, n
            )

    return -1


# Example
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 32

result = binary_search_recursive(
    list1, 0, len(list1) - 1, n
)

if result != -1:
    print("Element is present at index", result)
else:
    print("Element is not present in list1")

Output

Element is present at index 2

Binary Search Complexity

Case	Time Complexity
Best Case	O(1)
Average Case	O(log n)
Worst Case	O(log n)

Binary Search is efficient because each comparison eliminates approximately half of the remaining search space. For a large sorted list, this can significantly reduce the number of comparisons compared with Linear Search.

Binary Search vs Linear Search

Feature	Binary Search	Linear Search
Data Requirement	List must be sorted	List does not need to be sorted
Searching Method	Divides the search space	Checks elements sequentially
Best Case	O(1)	O(1)
Worst Case	O(log n)	O(n)
Approach	Divide and conquer	Sequential

Why is Binary Search Efficient?

Binary Search does not examine every element in the list. Instead, it removes half of the remaining search space after each comparison.

For example, when searching a list containing 1,000 elements, the algorithm does not need to check all 1,000 elements one by one. It repeatedly divides the possible search range, which makes the number of required comparisons much smaller.

Advantages of Binary Search

• Efficient for large sorted datasets.
• Has a worst-case time complexity of O(log n).
• Reduces the search space by half after each step.
• Can be implemented using iteration or recursion.
• Requires relatively few comparisons for sorted data.

Limitations of Binary Search

• The data must be sorted before searching.
• It is not directly suitable for an unsorted list.

YT:- DecodeIT

Conclusion

In this tutorial, we explored both iterative and recursive Binary Search. The iterative approach uses a loop, while the recursive approach repeatedly calls the same function with a smaller search range.

With a worst-case time complexity of O(log n), Binary Search is especially useful when searching large sorted datasets. Understanding this algorithm is an important step toward learning searching techniques, algorithms, and data structures in Python.

Frequently Asked Questions

What is Binary Search in Python?

Binary Search is an algorithm used to find an element in a sorted list by repeatedly dividing the search range into two parts.

Does Binary Search require a sorted list?

Yes. The standard Binary Search algorithm requires the data to be sorted so that it can correctly choose between the left and right portions.

What is the time complexity of Binary Search?

The best-case time complexity is O(1), while the average and worst-case time complexity is O(log n).

What are the two methods of Binary Search?

Binary Search can be implemented using an iterative method with a loop or a recursive method where the function calls itself.

Is Binary Search faster than Linear Search?

For large sorted datasets, Binary Search generally requires fewer comparisons because it reduces the search space by half at every step. Linear Search checks elements sequentially.

Keywords

Binary Search in Python, binary search in python with example, binary search in Python using for loop, binary search in Python inbuilt, binary search in Python using list, binary search in Python without function, binary search algorithm, Binary Search in Python algorithm, binary search in Python W3Schools, recursive binary search in Python, iterative binary search in Python, binary search vs linear search, searching algorithms in Python, Python data structures, binary search program in Python