Linear Search in Array using C++

Given an integer array Arr[] containing integer numbers in any order. The goal is to find the input integer val present in the array using recursive search on the array.

If val is not found in the input array Arr[] then return -1. Print the index of val if found in Arr[].

Examples

Input −Arr[] = {11,43,24,50,93,26,78} val=26

Output − 26 found at index 5

Explanation −

Elements in the array start from index 0 to index=array length -1.
First index=0 last index=6 : 11 != 26, 78 != 26 → 0+1 , 6-1
First index=1 last index=5 : 43 != 26, 26 = 26 return 5
26 is present at index 5.

Input − Arr[] = {11,43,24,50,93,26,78} val=66

Output − 66 is not present

Explanation −

Elements in the array start from index 0 to index=array length -1.
First index=0 last index=6 : 11 != 66, 78 != 66 → 0+1 , 6-1
First index=1 last index=5 : 66 != 26, 66 != 26 → 1+1 , 5-1
First index=2 last index=4 : 24 != 66, 93 != 66 → 2+1 , 4-1
First index=3 last index=3 : 50 != 26, 50 != 26 → 3+1 , 3-1
First index=3 last index=2 3>2 end
66 not found.

Approach used in the below program is as follows

In this approach we will traverse the array linearly from both ends. Compare input value with elements at both ends. If found, then return the index else recursively check for next elements with first index=prev first index+1 and last index=prev last index-1. In case first index>last index then element is not found.

• Take the input array Ar[] with integer elements.

• Take the element to be searched as val.

• Function searchRec(int arr[], int start,int end, int num) takes an array, first and last indexes and value num that is to be searched and returns the index if found.

• Take the variable result as -99.

• If arr[start] == num then set result as start

• If arr[end] == num then set result as end

• if (start > end) then set result=-1. As traversed whole array

• If result has value other than -99 then return result else search recursively using searchRec(arr, start + 1, end - 1, num)

• Inside main check return value and print result accordingly

Example

#include<bits/stdc++.h>
using namespace std;
int searchRec(int arr[], int start,int end, int num){
   int result=-99;
   if (start > end){
      result= -1;
   }
   if (arr[start] == num){
      result=start;
   }
   if (arr[end] == num){
      result=end;
   }
   if( result!=-99){
      return result;
   }
   return searchRec(arr, start + 1, end - 1, num);
}
int main(){
   int Arr[] = {11,43,22,56,33,26,78};
   int i;
   int len = sizeof(Arr) / sizeof(Arr[0]);
   int val = 56;
   int pos = searchRec(Arr, 0, len - 1, val);
   if (pos == -1){
      cout<<val<<" is not present" ;
   }
   else{
      cout<<val<<" found at index "<<pos;
   }
   return 0;
}

Output

If we run the above code it will generate the following Output

56 found at index 3