Updated March 30, 2023
Introduction to Binary search in Python
The following article provides an outline for Binary search in Python. A binary search is a searching algorithm that is used to find a particular element in a sorted array. It searches by repeatedly dividing the array into 2 halves in each iteration. It works on a divide and conquers approach. Comparison of the searched element is made with the middle element of the array and then decide which part of the array to continue the search. Binary search is considered to be one of the best algorithms when there are 1000 elements, and the user wants to search and get the index of a particular element. The only condition of using the binary search in a program is that the elements need to be sorted to implement it.
Syntax:
Below given is the basic syntax of using the Binary search in Python:
b_search(array, 0, array_len-1, element):
mid = low+high //2
if array[mid] == element:
# do something
elif array[mid] <= element:
b_search (array, mid+1, array_len-1, element)
else
b_search(array, 0, mid-1, element)
else
#do something (element not found)Where,
b_search: function searching for binary search having all the logic
array: list having all the elements stored in sorted order
How does Binary Search work in Python?
As we have understood, Binary search is used to search the element in a sorted array. It repeatedly divides the array into halves by comparing it with the middle element and proceeding towards the half with the element’s probability. Thus, it continues until it finds the element to be searched. Below given is the step by step procedure of how the Binary search works in Python:
1. Sort the elements of the array in ascending order (if not).
2. Suppose we have the sorted list of elements as:
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 |
and the element to be searched is 10.
3. The starting index is considered as ‘L’ and the last index as ‘R’. So now the middle element is calculated as:
mid = (L+H)/2In the above example,
mid = (0+7)/2
mid= 31. Now, the comparison is made between the mid element, i.e., 40 (in the above case), and the element to be searched, i.e., 10. If the element to be searched is equal to the mid element, the search is successful, and further searching can be terminated.
2. If the element to be searched is lower than the mid element, we will eliminate the values greater than the mid element of the array, i.e., all the values from 50 till last ‘H’ are eliminated. Now the H = mid-1. Again steps 3 and 4 are repeated.
- According to the above example, now H = 30, L=10.
- Again mid is calculated, now mid= (0+2)/2 = 1.
- Comparison is made between 10 (Element to be searched) and mid, i.e., 20. Since they are not equal and 10 is less than mid, we move to the left side of the array and so on.
3. If the element to be searched is higher than the mid element, we will eliminate the values less than the mid element, i.e., the left side array would be eliminated. Now L = mid+1. Again steps 3 and 4 are repeated.
Examples:
Binary search can be implemented either by using the Iterative approach or the Recursive approach to find the element in the array. But we have used the Recursive approach to implement the binary search below:
# Using the recursive function to implement binary search
def b_search(binary_array, L, H, ele):
# Checking the list is sorted or not
if L <= H:
#finding the middle element of the array
mid = (L + H) // 2
# If element to be searched is equal to middle element, it returns the index and program terminates
if binary_array[mid] == ele:
return mid
# If the element to be searched is smaller than the mid, search continues to the left side of the array.
elif binary_array[mid] > ele:
#now the H = mid-1 in the new search
return b_search(binary_array, L, mid - 1, ele)
# If the element is larger than the mid, search continues to the right side of the array
else:
#now the L = mid+1 in the new search
return b_search(binary_array, mid + 1, H, ele)
else:
#If the element to be searched is not present in the list
return -1
# Array containing the items in the sorted order.
binary_array = [12, 30, 56, 67, 87, 90, 101]
#element to be searched
ele = 90
# Calling the binary search function created above by passing the array, starting index,last index and the element to be searched
result = b_search(binary_array, 0, len(binary_array)-1, ele)
if result != -1:
print("Congratulations!! Your Element is present at "+ str(result+1)+ " position")
else:
print("Sorry!! Element you are searching is not present in the list")Output:
Explanation:
- In the above example, first, the binary_array having all the elements in the sorted order is defined.
- The element to be searched is defined in the ‘ele’ variable, which is 90.
- A function named ‘b_search’ is called by passing the above array of elements (binary_array), starting index(which is 0 in every case), last index (which is the length of array- 1), and the element (ele) to be searched.
- The result is stored in a variable named ‘result’.
- In the function ‘b_search’, the middle element ‘mid’ is calculated using (low+high)/2.
- If elif and else statements are used to compare the middle element ‘mid’ element with the element ‘ele’ to be searched.
- Simple binary search conditions are applied for the actions to be taken if the middle value is less than the element to be searched (make L = mid+1).
- If the middle value is higher than the element to be searched (make H = mid-1).
- ‘Mid’ index is returned if the element is found and -1 if the element to be searched is not found in the list.
- An appropriate message is printed on the console according to the result captured in the ‘result’ variable.
Conclusion
The above description clearly explains what binary search is and how it works in Python. Binary search is considered to be one of the best searching algorithms when the elements are stored in sorted order. Moreover, it is quite easy to implement. The searching speed is very fast as it skips the unnecessary comparisons by considering the only list close to the element to be searched.
Recommended Articles
This is a guide to Binary search in Python. Here we discuss How does Binary Search work in Python along with the examples and outputs. You may also have a look at the following articles to learn more –
