Binary Search in Python

September 14, 2023

Introduction to Binary Search in Python

Binary Search in Python enhance your search strategies using the binary search algorithm in Python. Acquire a step-by-step grasp of binary search implementation, comprehend its principles and real-world applications, and delve into practical instances. Leverage the advantages of logarithmic time complexity for swift data retrieval. Begin your journey towards becoming a proficient binary search practitioner today!

What is a Binary Search in Python? Binary search in Python is a highly efficient algorithmic technique used to locate a specific target value within a sorted collection, such as an array or a list.

What is Searching Technique?

Searching refers to the process of locating a specific element, value, or data within a collection, such as an array, list, or database.

In Python, searching can be categorized into two main types:

- Linear Search
- Binary Search

Binary Search in Python

Binary search is a fast and efficient algorithm for finding a target value within a sorted collection by repeatedly dividing the search space in half and quickly converging to the desired element.

Concept of Binary Search

Binary Search uses two methods to find the target element :

Recursive Method
Iterative Method

Note: Recursive Method is also known as "Divide and Conquer Method". This approach involves a function invoking itself repeatedly until it locates an element within the list.

How Binary Search in Python Works ?

The following steps are followed for finding element ‘x = 5′ from the given array :

1. Set two pointers low and high for the given array.

2. From the given array; find the middle element i.e. mid = (low+high)/2.

3. If x==mid, then simply return mid, else compare the element with the middle element.

4. If x>mid, then set low = mid+1 and find the middle element.

5. If x<mid, then set high = mid-1 and find the middle element.

6. Repeat steps 2 to 6 until we find the target element i.e. ‘x’.

7. If low=high, we found that element x=5.

Binary Search in Python Methods:

1. Recursive Method

The recursive method for binary search in Python involves breaking down the search process into smaller subproblems by dividing the sorted array into halves. At each step, the middle element is compared to the target value. If they are equal, the search is successful. If the middle element is greater than the target, the search recurs on the left half; if it’s smaller, the search recurs on the right half.

binarySearch(arr, x, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]        //when x is on the right side
            return binarySearch(arr, x, mid + 1, high)
        else                               //when x is on the left side
            return binarySearch(arr, x, low, mid - 1)

2. Iterative Method

In this method, the entire sorted array serves as the search range. In each iteration, the middle element of the current interval is compared to the target value. If they match, the search is successful. If the middle element is greater than the target, the interval is adjusted to the left half; if it’s smaller, the interval shifts to the right half. This process iterates until the interval becomes empty or the target is found.

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) //when x is on the right side
        low = mid + 1
    else                       // when x is on the left side
        high = mid - 1

Python Examples(Iterative Method)

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target_element = 11
result = binary_search_iterative(sorted_list, target_element)

if result != -1:
    print(f"Element {target_element} found at index {result} using iterative binary search")
else:
    print("Element not found")

Python Examples(Recursive Method)

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)


def binary_search_recursive_wrapper(arr, target):
    return binary_search_recursive(arr, target, 0, len(arr) - 1)

sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target_element = 11
result = binary_search_recursive_wrapper(sorted_list, target_element)

if result != -1:
    print(f"Element {target_element} found at index {result} using recursive binary search")
else:
    print("Element not found")

Time Complexity for Binary Search

The time complexity of the binary search algorithm in Python is O(1) for the best case and O(logn) for the worst and average case, where “n” represents the number of elements in the list or array being searched.

There are mainly three case for Time complexity :

- Best Case : O(1)
- Average Case : O(logn)
- Worst Case : O(logn)

Conclusion

Throughout this guide, we’ve delved into the intricacies of binary search, from its fundamental principles to its step-by-step implementation in Python. Remember that while binary search offers exceptional speed advantages, it’s essential to work with sorted data to fully leverage its benefits.

Searching Algorithm in Python

Linear Search in Python

Trie In Python

Making a trie Node Class

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Most Frequently Asked Questions and Answers

Question 1.

What are the advantages of binary search?

Explanation

Binary search has a logarithmic time complexity of O(log n), making it highly efficient for large datasets. It outperforms linear search (O(n)) for sorted arrays.

Question 2.

What happens if the array is not sorted for binary search?

Explanation

Binary search requires a sorted dataset. If the array is not sorted, the algorithm will not produce accurate results.

Question 3.

Can binary search be applied to linked lists?

Explanation

Yes, binary search can be applied to linked lists, but it’s less straightforward than with arrays due to the lack of direct indexing. It requires converting linked list elements into an array-like structure.

Question 4.

Are there any limitations to binary search?

Explanation

Binary search is limited to sorted datasets. It might not be the best choice for small datasets or datasets that frequently change, as sorting incurs an additional cost.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Binary Search in Python

Introduction to Binary Search in Python

What is Searching Technique?

Binary Search in Python

How Binary Search in Python Works ?

1. Set two pointers low and high for the given array.

2. From the given array; find the middle element i.e. mid = (low+high)/2.

3. If x==mid, then simply return mid, else compare the element with the middle element.

4. If x>mid, then set low = mid+1 and find the middle element.

5. If x<mid, then set high = mid-1 and find the middle element.

6. Repeat steps 2 to 6 until we find the target element i.e. ‘x’.

7. If low=high, we found that element x=5.

Binary Search in Python Methods:

1. Recursive Method

2. Iterative Method

Python Examples(Iterative Method)

Python Examples(Recursive Method)

Time Complexity for Binary Search

Conclusion

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription