#include<iostream>
using namespace std;
bool LinearSearch(int arr[], int size, int key){
// Base Case
if(size == 0) // If the array is empty
return false;
// If the element is present
if (arr[0] == key){
return true;
}
else{
bool remainingPart = LinearSearch(arr+1, size-1, key); // Recursive case
// Return true if the element is found in the remaining part of the array
return remainingPart;
}
}
int main(){
int arr[] = {1,2,3,4,5,6};
int size = sizeof(arr)/sizeof(arr[0]); //size of the array
int key = 10;
bool ans = LinearSearch(arr, size, key);
if(ans){
cout << " Key is present in Array" << endl;
}
else{
cout<< "Key is not present in Array" << endl;
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmJvb2wgTGluZWFyU2VhcmNoKGludCBhcnJbXSwgaW50IHNpemUsIGludCBrZXkpewoKICAgIC8vIEJhc2UgQ2FzZQogICAgaWYoc2l6ZSA9PSAwKSAvLyAgSWYgdGhlIGFycmF5IGlzIGVtcHR5CiAgICByZXR1cm4gZmFsc2U7CiAgICAKICAgIC8vIElmIHRoZSBlbGVtZW50IGlzIHByZXNlbnQKICAgIGlmIChhcnJbMF0gPT0ga2V5KXsgCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBlbHNlewogICAgICAgIGJvb2wgcmVtYWluaW5nUGFydCA9IExpbmVhclNlYXJjaChhcnIrMSwgc2l6ZS0xLCBrZXkpOyAgLy8gUmVjdXJzaXZlIGNhc2UKICAgICAgICAKICAgICAgICAvLyBSZXR1cm4gdHJ1ZSBpZiB0aGUgIGVsZW1lbnQgaXMgZm91bmQgaW4gdGhlIHJlbWFpbmluZyBwYXJ0IG9mIHRoZSBhcnJheQogICAgICAgIHJldHVybiByZW1haW5pbmdQYXJ0OwoKICAgIH0KCn0KCmludCBtYWluKCl7CiAgICBpbnQgYXJyW10gPSB7MSwyLDMsNCw1LDZ9OwogICAgaW50IHNpemUgPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsgLy9zaXplIG9mIHRoZSAgYXJyYXkKICAgIGludCBrZXkgPSAxMDsKICAgIGJvb2wgYW5zID0gTGluZWFyU2VhcmNoKGFyciwgc2l6ZSwga2V5KTsKICAgIGlmKGFucyl7CiAgICAgICAgY291dCA8PCAiIEtleSBpcyBwcmVzZW50IGluIEFycmF5IiA8PCBlbmRsOwogICAgfQogICAgZWxzZXsKICAgICAgICBjb3V0PDwgIktleSBpcyBub3QgcHJlc2VudCBpbiBBcnJheSIgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwoKfQ==