Mastering Binary Search: Unveiling the Recursive Approach

Introduction

Hi, Folks. In the world of algorithms and data structures, binary search stands as the first option for efficient searching in sorted arrays. While the iterative version of binary search is widely known, the recursive adaptation offers a unique perspective on problem-solving and master recursion.

Idea Behind the Binary Search

The binary search algorithm works in the concept of divide and conquer. At its core, binary search aims to efficiently locate a target value within a sorted array by repeatedly dividing the search space in half.

The efficiency of binary search arises from its ability to eliminate half of the remaining possibilities with each step.

Iterative implementation

// Binary Search is implemented using an iterative function.
let iterativeFunction = function (sorted_arr, target) {
   let start = 0,
      end = sorted_arr.length - 1;

   // Iterate as long as the beginning does not encounter the end.
   while (start <= end) {
      // find out the middle index
      let mid = Math.floor((start + end) / 2);

      // Return True if the element is present in the middle.
      if (sorted_arr[mid] == target) return true;
      // Otherwise, look in the left or right half
      else if (sorted_arr[mid] < target) start = mid + 1;
      else end = mid - 1;
   }

   return false;
};

// input & initiation code
let sorted_arr = [2, 6, 8, 10, 12, 14];
let target = 9;

Iterative implementation is easy to understand what is happing but the scope of this article is to explain the recursive approach of the binary search.

As we delve into the recursive approach to binary search, we'll witness how this fundamental concept can be elegantly expressed through recursive algorithms, enabling us to unlock the potential of both binary search and recursion in problem-solving.

---

Recursion

Recursion in programming refers to a technique where a function calls itself to solve a problem. It is a fundamental concept that allows a function to break down a complex problem into simpler, more manageable instances of the same problem.

Explaining the basics of recursion is out of the scope of this article. For a better understanding check out the article Recursion & Memory Visualization.

Dry run

The broad strategy is to look at the middle item on the list. The procedure is either terminated (key found), the left half of the list is searched recursively, or the right half of the list is searched recursively, depending on the value of the middle element.

Let's check the implementation first & then the execution stack.

Call Stack

As we know the recursion has an induction the return value is returned to the function where it is called so it returns the value once it is found.

The base condition (start > end) . This means there is no more element present in the array so it returns -1.

Conclusion

In conclusion, the recursive binary search algorithm stands as a testament to the elegance and efficiency that can be achieved through the power of recursion and divide-and-conquer strategies.

Share & comment your thoughts on it for more content like this.