Binary Search using Recursion in Python

We split a collection of items into two halves in Binary Search to decrease the number of direct comparisons needed to discover an element. However, there’s one requirement: the array’s items must be sorted beforehand.

Binary Search

The Binary Search Method locates the index of a certain list member. It is among the most popular and quickest algorithms. For the Binary Search procedure to operate, the entries in the list should be sorted.

Binary Search is a more efficient search technique for locating an element’s index than Linear Search since we don’t have to examine every list index.

The Binary Search Algorithm’s whole operation may be summarized in the following steps:

• Locate the middle element in the sorted array.
• Make a comparison between the element to be located and the middle element.
• If that element is equal to the middle element of the given list, then the index of the middle element is returned. Otherwise, the algorithm will compare the element with the item in the middle.
• Now, if the element to be located is greater than the middle item of the list, it will be compared to the right half of the list, i.e., elements after the middle index.
• Or if the element is less than the element at the middle of the list, then it will be compared to only the left half of the list, i.e., elements before the middle index.

Recursive Binary Search

Binary Search implies continually dividing the searching interval into 2 equal parts to discover an element in a sorted array, and recurrent binary Search entails breaking down the complete binary search procedure into smaller issues. A recursive binary search is the recursion answer to a binary search.

The following are the characteristics that all-recursive solutions must meet:

1. A base case is required for a recursive approach.
2. There must be a recursive test case in a recursive approach.
3. A recursive approach has to get nearer to the base case.

The lowest subdivision of a complicated problem is represented by a base case, which is a final case. So, to perform the binary Search by recursive method, our algorithm must contain a base case and a recursive case, with the recursive case progressing to the base case. Else the process would never finish and result in an endless loop.

The binary search technique reduces the time it takes to find a specific element inside a sorted array. The binary search method is often implemented iteratively, but we may also implement it recursively by breaking it down into smaller pieces.

Code

Output:

The given list is
[2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22]
Element searched is found at the index 2 of given list

Recursion is an extremely powerful programming and problem-solving technique. We may use it to evaluate and execute a variety of algorithms, ranging from simple iterative issues to complicated backtracking problems. In this tutorial, we looked at using the Python language to create the recursive binary search method.