Binary Search in Python - Scaler Topics

The process of finding an element from a collection of elements is known as searching. We have several techniques or ways of searching an element among several given elements, and these techniques are known as searching algorithms. Binary Search is one of the easiest search algorithms. Let us learn about the binary search in Python.

Binary Search in Python is a searching technique that works on a sorted array or list of elements. Instead of comparing every element of the list with the required element, the binary search algorithm repeatedly divides the list of elements into smaller segments. It then searches for the required element in the divided segments.

Recursive Binary Search

The recursive implementation of the binary search algorithm involves defining a recursive function that performs the search. It takes the sorted array, the target value to search for, and the range of indices to consider in the current recursive call.

Let us first know the recursive way. Suppose we want to search element E in the array.

We can call a function on the array with the required element E: BinarySearch(array, E). This function will return the index the element E.

Steps Involved in the Recursive Approach

Compare E with the mid element.
If $E == array[mid]$ , then we return the mid index.
Else if $E > array[mid]$ , call the function BinarySearch function on the left half of the array.
Else we call the function BinarySearch on the right half of the array.

Note:

We have to perform the above steps by keeping in mind the base condition that the low index should always be less than or equal to the high index.

Code:

Output:

Iterative Binary search

Iterative Binary Search is a search algorithm used to find a specific target value within a sorted array. It follows the principle of the Binary Search algorithm but utilizes an iterative approach instead of recursion.

Let us now discuss the iterative approach to implement binary search. Suppose, we want to search the same element E in the array.

We can call a function on the array with the required element E: BinarySearch(array, E). This function will return the index of element E.

Steps Involved in Iterative Approach

Compare E with the mid element.
If $E == array[mid]$ , then we return the mid index.
Else if $E > array[mid]$ , then we shift the low index to mid + 1.
Else, we shift the high index to mid - 1.

Code:

Output:

Binary Search Complexity

The time complexity of binary search in Python is better than linear search because we do not need to search over the entire array. We smartly divide the array into smaller sub-arrays and get our answer. So, binary search is a faster and more efficient algorithm, but it only works on the sorted array.

Time Complexity

When the desired element is directly found at the middle index, we get the best time complexity i.e., $O(1)$ . On the other hand, if we cannot find the required element in the entire array, then we get the worst time complexity, i.e., $O(log n)$ . The space is constant.

The average time complexity of the binary search in Python is $O (log n)$ .

Space Complexity

We do not need any extra variable or data structure to find the result. So, the space complexity of the binary search is $O(1)$ .

FAQs

Q. What is the difference between Binary Search and Linear Search?

A. Binary Search and Linear Search are two different algorithms used for searching elements in an array. Binary Search is an efficient algorithm that requires the array to be sorted and continually divides the search space in half, resulting in a time complexity of O(log n). On the other hand, Linear Search sequentially checks each element in the array until the target value is found or the end of the array is reached, resulting in a time complexity of O(n). Binary Search is significantly faster for large sorted arrays compared to Linear Search.

Q. Can Binary Search be applied to non-numeric data or custom objects?

A. Yes, Binary Search can be applied to non-numeric data or custom objects in Python. However, for Binary Search to work correctly, the data or objects must have a defined ordering. This ordering can be established by implementing comparison functions or operators that define the criteria for sorting and comparison.

Q. What happens if the array is not sorted in Binary Search?

A. If the array is not sorted, Binary Search cannot be directly applied. Binary Search relies on the array being sorted to divide the search space efficiently. In such cases, it is necessary to sort the array using a sorting algorithm (such as Python's built-in sort function or custom implementation) before performing Binary Search.

Q. Are there any limitations or prerequisites for using Binary Search?

A. Binary Search has a few prerequisites and limitations. Firstly, the array must be sorted in ascending or descending order. Additionally, the Binary Search algorithm assumes that the array elements are comparable using equality and relational operators. If the array contains duplicate values, Binary Search may not always return the first occurrence of the target value. To address this, additional logic can be added to handle such scenarios if necessary.

Conclusion

Binary Search in python is a searching technique that works on a sorted array or list of elements.
The binary search algorithm repeatedly divides the list of elements into smaller segments and then searches the required element in the divided segments.
Binary Search follows the principle of the divide and conquer technique.
Binary Search is better than linear search.
Binary Search is one of the fastest searching algorithms.
We can implement binary search both iteratively and recursively.
The average time complexity of the binary search in Python is $O (log n)$ , and the space complexity of the binary search in Python is $O(1)$ .