write a program to implement binary search on list in p;ython

 

Binary Search in Python

This tutorial will learn how we can apply a binary search algorithm using Python to find an element's index position in the given list.

Concept of Binary Search

In the binary search algorithm, we can find the element position using the following methods.

• Recursive Method
• Iterative Method

The divide and conquer approach technique is followed by the recursive method. In this method, a function is called itself again and again until it found an element in the list.

Implement a Binary Search in Python

First, we implement a binary search with the iterative method. We will repeat a set of statements and iterate every item of the list. We will find the middle value until the search is complete.

Let's understand the following program of the iterative method.

Python Implementation

1. # Iterative Binary Search Function method Python Implementation  
2. # It returns index of n in given list1 if present,   
3. # else returns -1   
4. def binary_search(list1, n):  
5.     low = 0  
6.     high = len(list1) - 1  
7.     mid = 0  
8.   
9.     while low <= high:  
10.         # for get integer result   
11.         mid = (high + low) // 2  
12.   
13.         # Check if n is present at mid   
14.         if list1[mid] < n:  
15.             low = mid + 1  
16.   
17.         # If n is greater, compare to the right of mid   
18.         elif list1[mid] > n:  
19.             high = mid - 1  
20.   
21.         # If n is smaller, compared to the left of mid  
22.         else:  
23.             return mid  
24.   
25.             # element was not present in the list, return -1  
26.     return -1  
27.   
28.   
29. # Initial list1  
30. list1 = [12, 24, 32, 39, 45, 50, 54]  
31. n = 45  
32.   
33. # Function call   
34. result = binary_search(list1, n)  
35.   
36. if result != -1:  
37.     print("Element is present at index", str(result))  
38. else:  
39.     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

1. # Python program for recursive binary search.  
2. # Returns index position of n in list1 if present, otherwise -1  
3. def binary_search(list1, low, high, n):   
4.   
5.    # Check base case for the recursive function  
6.    if low <= high:  
7.   
8.       mid = (low + high) // 2  
9.   
10.       # If element is available at the middle itself then return the its index  
11.       if list1[mid] == n:   
12.          return mid   
13.   
14.       # If the element is smaller than mid value, then search moves  
15.       # left sublist1  
16.       elif list1[mid] > n:   
17.          return binary_search(list1, low, mid - 1, n)   
18.   
19.       # Else the search moves to the right sublist1  
20.       else:   
21.          return binary_search(list1, mid + 1, high, n)   
22.   
23.    else:   
24.       # Element is not available in the list1  
25.       return -1  
26.   
27. # Test list1ay   
28. list1 = [12, 24, 32, 39, 45, 50, 54]  
29. n = 32  
30.   
31. # Function call   
32. res = binary_search(list1, 0, len(list1)-1, n)   
33.   
34. if res != -1:   
35.    print("Element is present at index", str(res))  
36. else:   
37.    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.