Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you’ve narrowed down the possible locations to just one. In this tutorial, I will show you how to implement binary search algorithms using python.
Well, before jumping this tutorial, you have to knowledge about recursion. Recursion is a programming technique. That is a function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.
Binary search using recursion in python
Implement binary search, your array or list must have sorted data. Otherwise, you can’t apply a binary searching algorithm. Let’s see the following code, I will explain you later.
def binary_search(arr, left, right, val): if right >= left: mid = (left + right) // 2 if arr[mid] == val: return mid elif arr[mid] > val: return binary_search(arr, left, mid-1, val) elif arr[mid] < val: return binary_search(arr, mid + 1, right, val) else: return -1
Well, now I will explain to you how this binary_search function works. This function takes four parameters. They are the array or list, the second parameter is the left index, the third parameter is a right index and the last perimeter is the targeted value. That is we have to check exists or not. If the targeted value exists then return its index otherwise return -1. That is denoted this value doesn’t exist in the list or array.
Then check a condition, that is the value of right is greater than or equal to left value. Inside the conditions, take a variable that stores our targeted value’s index. After then calculate the mid-value of the given array. The first left and right values are then divided by two. Then check array[mid] equal to our targeted value then return mid-value. If the mid-value is not equal to the targeted value then you have to call again this function.
In essence, You have to call it recursively with conditions. The conditions are if array[mid] is greater than our targeted value then you have to change the right and left value. Look at avobe code how to I do it. Do the same task for arra[mid] is lower than the targeted value.
def binary_search(arr, left, right, val): if right >= left: mid = (left + right) // 2 if arr[mid] == val: return mid elif arr[mid] > val: return binary_search(arr, left, mid-1, val) elif arr[mid] < val: return binary_search(arr, mid + 1, right, val) return -1 # arr = [100, 50, 40, 10, 60, 70, 80, 400, 30] brr = [10, 20, 30, 40, 50] l = len(brr) ind = binary_search(brr, 0, l-1, 100) print(l)
The time complexity of the binary search is O(logn).