Binary Search in Python

In Python, the binary search technique is utilized to locate a specific element within a list. Consider a list containing a thousand elements, where we aim to determine the index of a certain element. The binary search algorithm allows us to quickly ascertain the index position of that element.

Numerous search algorithms exist, yet the binary search stands out as the most widely recognized among them.

In order to utilize the binary search algorithm, the items in the list need to be arranged in a sorted order. If the elements are not sorted, it is essential to sort them prior to execution.

Let's understand the concept of binary search.

Concept of Binary Search

The binary search algorithm allows us to determine the position of an element through these approaches:

• ✅ Recursive Approach
• ✅ Iterative Approach

The recursive method employs the divide and conquer strategy. In this approach, a function repeatedly invokes itself until it locates an element within the list.

A series of statements is executed repeatedly to determine the index position of an element using the iterative approach. The while loop facilitates this process.

Binary search outperforms linear search as it eliminates the need to examine every index in the list. For the binary search algorithm to function correctly, the list must first be sorted.

We will now proceed with a detailed, step-by-step execution of the binary search algorithm.

We possess an ordered collection of elements, and we are seeking the index location of 45.

[12, 24, 32, 39, 45, 50, 54]

In our list, we establish two pointers. The first pointer indicates the lower value, referred to as low, while the second pointer signifies the upper value, known as high.

Subsequently, we determine the value of the central element within the array.

mid = (low+high)/2

Here, the low is 0 and the high is 7.

mid = (0+7)/2

mid = 3 (Integer)

Next, we will evaluate the searched element against the value at the mid index. Here, 32 does not match 45. Thus, additional comparisons are required to locate the element.

If the target number matches the mid value, return mid; if not, proceed with the subsequent comparison.

If the target number exceeds the middle value, we then compare n with the middle element among the elements located to the right of mid and adjust low to low = mid + 1.

Alternatively, compare n with the central element among the items located to the left of mid, and adjust high to high = mid - 1.

Continue the process until the desired number is located.

Implement a Binary Search in Python

Initially, we will execute a binary search using an iterative approach. This involves looping through a defined series of statements while examining each element of the list. We will identify the midpoint continuously until the search concludes.

Let us examine the subsequent program that utilizes the iterative approach.

# 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 us explore the recursive approach to binary search.

Recursive Binary Search

The binary search can utilize the recursion technique. In this approach, we will establish a recursive function that continually invokes itself until it satisfies the specified condition.

Recursive Binary Search Example in Python

Let us analyze the previously mentioned program through the lens of the recursive function.

# 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 final section, we have composed our primary program. It mirrors the earlier program, with the sole distinction being that we have supplied two parameters to the binary_search function.

This occurs because we are unable to set the initial values for low, high, and mid within the recursive function. Each invocation of the recursion resets these variables, leading to incorrect outcomes.

Complexity

The binary search algorithm exhibits a complexity of O(1) in the best-case scenario. This occurs when the target element is identified in the initial comparison. The complexity for both the worst-case and average-case scenarios is O(log n). This is contingent on the number of comparisons made to locate the desired element.

Conclusion

The binary search algorithm represents the most effective and rapid method for locating an element within a list. It avoids unnecessary comparisons. As indicated by its name, the search process is split into two segments. It concentrates on the portion of the list that is nearer to the target number we are attempting to find.

We have examined both approaches to determine the index location of the specified number.