Divide and Conquer Algorithm for Linear Search

Divide and Conquer Algorithm for Linear Search

We have seen the Binary Search Algorithm which searches for an element in a sorted array in logarithmic time. Time complexity associated with it is . 

Recurrence relation of Binary Search: 

Using the same principle of Divide, Conquer, and Combine, we can also utilize this algorithm to find an element in an unsorted array, though the time complexity will be linear .

Recurrence relation of Linear Search: 

#include<iostream>

#include<vector>

using namespace std;

int linear_search(vector<int>&v,int s,int e,int x)

{

    if(s>e)return -1;

    int m=s+(e-s)/2;

    if(v[m]==x)return m;

    int left=linear_search(v,s,m-1,x);

    int right=linear_search(v,m+1,e,x);

    if(left==-1 && right==-1)return -1;

    if(left!=-1)return left;

    else if(right!=-1)return right;

}

int main()

{

    vector<int>v={4,2,6,8,1,2,9,4};

    cout<<linear_search(v,0,v.size()-1,8);

    return 0;

}

Output: 3

Analysis of time complexity: