Python is widely utilized for a variety of applications, including the development of websites, data analysis, and machine learning. Python programmers often encounter the problem of finding an element within an array or list. There are many approaches to doing this task, but binary search is one of the simplest and most efficient.

This article provides a complete guide on performing Python binary searches using various methods.

What is Binary Search in Python?

“Binary Search” is a technique that allows us to get an item/element in a sorted list or array. This technique works in logarithmic time complexity which means that the time required to search grows proportionally to the logarithm of the size of the list or array. This is much faster than “linear search”, which requires scanning the entire list or array until we find the element or reach the end.

How Does Binary Search Work in Python?

The “Binary Search” works on a simple principle:

• We start by comparing our element to the middle element of the list or array.
• If they are equal, we have found/determined the element and we can retrieve its index.
• If they are not equal, we can eliminate half of the list or array from further consideration, depending on whether the element we are looking for is smaller or larger than the middle element.
• This process is repeated with the remaining half until we either find the element or conclude that it does not exist in the list or array.

How to Perform Binary Search Technique in Python?

There are the following two ways to perform binary search in Python:

• “Iterative” Method.
• “Recursive” Method.

Method 1: Implementing Binary Search Utilizing the “Iterative” Method

In the “Iterative” method, a binary search is first implemented by repeating a set of statements and iterating each item until the middle value is reached.

Example

This example implements binary search in Python with the “Iterative” method:

In the above code:

• The user-defined function named “binary_search()” is defined and accepts list and target values as its arguments.
• The variable named “low” and “high” is initialized which specify the beginning and end of the list, respectively.
• The “while” loop continues as long as the “low” variable value is less than or equal to the “high” variable.
• This function determines the middle index of the list named “mid” and compares the target value to that index. If the target value is equal to the value at the middle index, the function retrieves the middle index.
• Otherwise, the function updates “low” or “high” depending on whether the target value is greater than or less than the value at the middle index.
• The function continues iterating until “low” is greater than “high”, which indicates that the target value is not in the list. In this case, the function returns “-1”.

Output

Method 2: Implementing Binary Search Using the “Recursive” Method

“Binary Search” can also be performed by utilizing the recursive function. This function keeps calling itself until a condition is met.

Example

The below code is used to implement the binary search utilizing the “Recursive” approach:

According to the above code:

• The “binary_search()” function takes the list, target value, and starting and ending index of the search interval as its arguments, respectively.
• The “if” statement is employed to determine if the “start_index” is greater than the “end_index”.
• Also, “-1” will be returned in the output which indicates that the target value is not in the list.
• Next, the middle index of the list is calculated, and the “if” condition is used to check if the value at the middle index of the list is equal to the target value. If it is, the specified function retrieves the middle index.
• If the above “if” condition is not satisfied, the “elif” condition checks if the value at the middle index of the list is less than the target value. If so, the function calls itself recursively from “middle + 1” to end.
• The “else” condition is executed if the value at the middle list index is greater than the target value. In this case, the function recursively calls itself, starting from the start index and ending at the “middle index – 1”.
• After defining the function, create a list and assign a value to the target variable.
• The “binary_search()” function is invoked that takes the value of the list, the target value, and the start and end indexes. This function retrieves the index value of the target, or “-1” if the target does not exist.
• The “if” and “else” condition is used to check if the index returned by the recursive function is “-1” or not.
• If so, the target value is not in the list, so the function prints “Target not found“. Otherwise, the message “Target found at index” is returned, followed by the index of the target value.

Output

Conclusion

The “Binary Search” in Python is a fast and efficient way to find an element in a sorted list and can be achieved via “iterative” or “recursive” approaches. Both methods divide the list into smaller segments and focus on the middle value until the element is found. This blog elaborated on the Python “Binary Search”.