Binary Search in Python

Concept of Binary Search in Python

• The basic concept behind binary search is that rather than comparing the required element to all of the array's elements, we will try comparing the required element to the array's middle element.
   
• The search is complete if it turns out to be the element we're looking for.
   
• Otherwise, since this array is sorted, if the element we are searching for is less than the middle element, we can be sure that it is in the first half or left half of the array.
   
• Similarly, if the element we're looking for is bigger than the middle element, it's likely in the array's second half.
   
• You can use Recursion or iteration to implement this method in the binary search process. We will discuss these approaches separately below.

Working on Binary Search in Python

For finding an element in an array, we can use binary search. It is preferred over simple linear search as its time complexity is O(log(n)), which is less than linear search's O(n). 

It is important to note that we can apply binary search only on monotonically increasing or decreasing arrays, i.e., sorted arrays. So first, you should make sure that the array is sorted, and then only we can apply binary search in our Python code.

Binary search works on a technique known as divide and conquer. In divide and conquer, we generally divide the large problem into smaller sub-parts and solve them.

Hence, in Binary search, we divide the array in half by finding the middle element and comparing that middle element with the target element that we need to search for in the array. This means that the search space is reduced to half at each iteration.

The image below depicts the steps involved in binary search. 

 Steps in binary search

1. Finding the middle element
    
2. Comparing the middle element with the required element

• If middle element is equal to the required element then return the position
   
• If middle element < required element; l-mid+1 (searching in the right part)
   
• If middle element > required element; h=mid-1 (searching in the left part)
   

First, the middle element of the sorted array is compared to the target element. If the middle element is equal to the required element, then we can simply return.

But if this is not the case, then, since we know that the array is sorted, if the middle element is less than the target element, then there is no use in searching for it in the left part of the middle element, as values will be obviously less than the target element.  So, our search space is reduced to half, as now we know that we need to search for the required element on the right side of the array.

Similarly, if the middle element is greater than the target element, then we need to search in the left part. So, we follow the same procedure repeatedly by comparing the middle element with the target element by dividing the search space. 

Implementation of Binary Search in Python

Binary search is a fundamental algorithm used for efficiently searching for a specific item within a sorted list or array. We'll explore the implementation of this decisive algorithm step by step.

1. Iterative Method

We'll iterate through the entire list in this method, repeating a series of instructions. We'll keep looking for the midpoint until we find it. For a better understanding, let's look at the algorithm, followed by the code.

Algorithm

1. Create a binarySearch() function with four parameters (arr, l, h, ele).
    
2. Declare two variables to hold the list's highest and lowest values.
    
3. Run the loop until the lowest and highest points meet:

mid = (l + h)/2
	if (ele == arr[mid]) 
	return mid 
else if (ele > arr[mid]) 
	l = mid + 1,  ele is on the right side
else 
	h = mid - 1, ele is on the left side

 

4. Initiate the array and the element to be discovered.
 

5. If the element is found, print the resulting position; otherwise, print the element not found .

Iterative Method Python Implementation

Output:

Complexities

Time Complexity: O(log n), where n is the array size.

Space Complexity: O(1)

2. Recursive Method

Binary Search uses the recursion approach as well. We'll write a recursive function that calls itself until the condition is satisfied. The recursive approach is based on the divide and conquer method, which involves breaking down a complex problem into smaller sub-problems, solving them, and then combining them to achieve the desired result. For a better understanding, let's look at the algorithm, followed by the code.

Algorithm

1. Create a binarySearch() function with four parameters (arr, ele, l, h).
    
2. Then proceed as follows until the lowest and highest points meet:
   mid = (l + h) / 2 
   if ele == arr[mid] return mid 
   else if ele > arr[mid], ele is on the right 
   return binarySearch(arr, ele, mid + 1, h) 
   else  ele is on the right 
   return binarySearch(arr, ele, l, mid - 1)
    
3. Initiate the array and the element to be discovered.
    
4. If the element is found, print the resulting position; otherwise, print the element not found.

Recursive Method Python Implementation

Output:

Complexities

Time Complexity: O(log n), where n is the array size.

Space Complexity: O(log n), as recursion creates Call Stack.

Binary Search Python Applications

Binary search has a wide number of applications. Below are some of the applications of binary search.

• Using binary search, we can optimize our approach to solve problems resulting in less time complexity.
   
• We can apply binary search to data structures such as trees and graphs. Using it, we can solve a number of problems, for example, insertion, searching, or deleting an element in BST (binary search tree).
   
• We can use binary search to find the peak element in the array. A peak element is defined as the number in an array that is strictly greater than the elements on its left and right.
   
• We can apply binary search in multiple problems related to bit manipulations.
   
• Binary search is used in range queries related scenarios. This means when we need to find a specific range sum or minimum/ maximum between a certain range.

Advantages of Binary Search in Python

• Binary search is highly efficient for sorted data, with a time complexity of O(log n), making it faster than linear search (O(n)).
   
• The algorithm is straightforward to implement and understand, involving repeated division of the search space.
   
• Binary search can be applied to various data structures, such as arrays and trees, as long as the data is sorted.
   
• It is handy for large datasets where linear search would be impractical due to its linear time complexity.

Disadvantages of Binary Search in Python

• Binary search requires that the data be pre-sorted. Sorting can be time-consuming for dynamic datasets.
   
• It only works well with dynamic data frequently changing, as maintaining sorted order is costly.
   
• It may require additional memory for recursive calls, which can be a drawback for large datasets.
   
• Binary search is primarily suitable for retrieval tasks and not for inserting or deleting elements within the data.

Frequently Asked Questions

Why is it called binary search?

Binary search is called so because it divides the search interval in half at each step, choosing the interval where the target value may exist. This binary division strategy quickly narrows down the search area, enhancing efficiency.

What is binary search syntax?

Binary search in Python is generally implemented using a while loop. The basic syntax involves defining a search range and iteratively checking it down until the target element is found or the search range is exhausted.

What is the fastest search algorithm in Python?

In Python, binary search is one of the fastest search algorithms for sorted data with a time complexity of O(log n). However, its efficiency depends on the data structure being searched. For unsorted data, hashing-based algorithms like set lookups are usually faster.

How to do binary search Python code?

To perform a binary search in the list in Python, we must ensure the list is sorted and initialize the starting and ending index. Then we must find the middle element and compare it to the target element. The search space is reduced to half at each iteration.

Conclusion

In this article, we have gone through the basic concept of binary search python, the two approaches, and the implementation of binary search in Python, as well as their complexities and real-world applications. Binary Search is an important algorithm used in solving a lot of problems. For taking your preparation journey to the next level, you can read more such descriptive articles on our platform. 

 

Recommended problems -

• Leaf Nodes in Binary Tree
• Vertical Order Traversal of a Binary Tree
• Binary Array Sorting
   

Happy Learning!