Using Divide and Conquer in Linear Search

Photo by Negative Space from Pexels

Before we go to the topic let’s do some basic revision.

Linear Search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. https://www.wikiwand.com/en/Linear_search

and,

Divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type until these become simple enough to be solved directly. https://www.wikiwand.com/en/Divide-and-conquer_algorithm

According to me, Linear Search is the most basic algorithm. It is pretty straight forward and easiest to implement. So naturally, every programmer knows this.

It doesn’t matter whether you are self-taught or learned to program in school or college, 90% chances are that you know how to implement linear search by simple iteration, And frankly, it is the best and only practical way!

So what’s the point of this post then?

Let’s come to it.

Think about the divide and conquer technique. As per the definition you have to recursively divide the bigger problem into two or more smaller problems. So basically we are diving and ruling. Now it doesn’t matter if you are dividing the problem into exactly two equal halves or many different smaller parts or some kind of uneven distribution.

Now we use this fact in the Linear search algorithm.

Let's look at the Iterative approach

Iterative Solution for Linear Search

Let’s see the Recursive approach

Recursive Solution for Linear Search(or Divide and Conquer)

What’s going on here?

We are calling a function and giving it an array, size of the array, element to search, and index as argument.

Inside the function, we are doing some basic checks and finally, we are calling the function again and this time we are incrementing the index by 1 (cause initially it was 0).

If you are confused that how this can be a divide and conquer, then please take a look at the definition again. It says to divide the problem into two or more parts and here we are dividing our array into an array of size one less than the original one.

But,

Here’s a catch. To apply it recursively can be good if you want to trick some beginner but for practical uses, this is as useless as it can be.

We are taking comparatively more resources and then also we have to complexity of O(n).

The main takeaway is to use the iterative method for linear search but if you want to have some fun then give someone this program.

For me, it was a different way to look at problems.

Thanks for reading! Good Day!