Binary Search in Python

Python Implementation

# Iterative Binary Search Function method Python Implementation  
# It returns index of n in given list1 if present,   
# else returns -1   
def binary_search(list1, n):  
    low = 0  
    high = len(list1) - 1  
    mid = 0  
  
    while low <= high:  
        # for get integer result   
        mid = (high + low) // 2  
  
        # Check if n is present at mid   
        if list1[mid] < n:  
            low = mid + 1  
  
        # If n is greater, compare to the right of mid   
        elif list1[mid] > n:  
            high = mid - 1  
  
        # If n is smaller, compared to the left of mid  
        else:  
            return mid  
  
            # element was not present in the list, return -1  
    return -1  
  
  
# Initial list1  
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 45  
  
# Function call   
result = binary_search(list1, n)  
  
if result != -1:  
    print("Element is present at index", str(result))  
else:  
    print("Element is not present in list1")  

Output:

Element is present at index 4

Explanation:

In the above program -

• We have created a function called binary_search() function which takes two arguments - a list to sorted and a number to be searched.
• We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, high to len(list1) - 1 and mid as 0.
• Next, we have declared the while loop with the condition that the lowest is equal and smaller than the highest The while loop will iterate if the number has not been found yet.
• In the while loop, we find the mid value and compare the index value to the number we are searching for.
• If the value of the mid-index is smaller than n, we increase the mid value by 1 and assign it to The search moves to the left side.
• Otherwise, decrease the mid value and assign it to the high. The search moves to the right side.
• If the n is equal to the mid value then return mid.
• This will happen until the low is equal and smaller than the high.
• If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.

Let's understand the recursive method of binary search.

Recursive Binary Search

The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.

Let's understand the above program using the recursive function.

Python Program

# Python program for recursive binary search.  
# Returns index position of n in list1 if present, otherwise -1  
def binary_search(list1, low, high, n):   
  
   # Check base case for the recursive function  
   if low <= high:  
  
      mid = (low + high) // 2  
  
      # If element is available at the middle itself then return the its index  
      if list1[mid] == n:   
         return mid   
  
      # If the element is smaller than mid value, then search moves  
      # left sublist1  
      elif list1[mid] > n:   
         return binary_search(list1, low, mid - 1, n)   
  
      # Else the search moves to the right sublist1  
      else:   
         return binary_search(list1, mid + 1, high, n)   
  
   else:   
      # Element is not available in the list1  
      return -1  
  
# Test list1ay   
list1 = [12, 24, 32, 39, 45, 50, 54]  
n = 32  
  
# Function call   
res = binary_search(list1, 0, len(list1)-1, n)   
  
if res != -1:   
   print("Element is present at index", str(res))  
else:   
   print("Element is not present in list1")  

Output:

Element is present at index 2

Explanation

The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.

• We calculate the middle number as in the last program.
• We have used the if statement to proceed with the binary search.
• If the middle value equal to the number that we are looking for, the middle value is returned.
• If the middle value is less than the value, we are looking then our recursive function binary_search() again and increase the mid value by one and assign to low.
• If the middle value is greater than the value we are looking then our recursive function binary_search() again and decrease the mid value by one and assign it to low.

In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the binary_search() function.

This is because we can't assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.

Complexity

The complexity of the binary search algorithm is O(1) for the best case. This happen if the element that element we are looking find in the first comparison. The O(logn) is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.

Conclusion

A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.

We have discussed both methods to find the index position of the given number.