Last active
June 4, 2022 20:35
-
-
Save anishshobithps/8cf9a35675c69312259176290c3685f1 to your computer and use it in GitHub Desktop.
Implementation of Quadratic Search in c++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Implementation of Quadratic Search in c++ | |
* Research Paper : https://research.ijcaonline.org/volume65/number14/pxc3886165.pdf | |
* Author : Parveen Kumar | |
* Code Author: Anish Shobith P S | |
*/ | |
#include<bits/stdc++.h> | |
class QuadraticSearch | |
{ | |
private: | |
std::vector<int> a; | |
int n, i, ele, loc = -1; | |
public: | |
void inputData(); | |
int search(); | |
void display(); | |
}; | |
void QuadraticSearch::inputData() | |
{ | |
std::cout<<"Enter the size of the array = "; | |
std::cin>>n; | |
int input; | |
std::cout<<"Enter the elements into the array = \n"; | |
for (i = 0; i < n; i++) | |
{ | |
std::cin>>input; | |
a.push_back(input); | |
} | |
std::cout<<"Enter the element to be searched = "; | |
std::cin>>ele; | |
} | |
int QuadraticSearch::search() | |
{ | |
int P1 = 0,P2 = 0,MID = 0, FIRST = 0, LAST = n - 1; | |
while(FIRST <= LAST) | |
{ | |
MID = (FIRST + LAST) / 2; | |
P1 = FIRST + (LAST- FIRST) / 4; | |
P2 = FIRST + (LAST- FIRST) * 3 / 4; | |
if (ele == a[MID] || ele == a[P1] || ele == a[P2]) | |
{ | |
loc = ele == a[MID] ? MID : ele == a[P1] ? P1 : P2; | |
return loc; | |
} | |
else if(ele < a[MID] && ele < a[P1]) | |
LAST = P1 - 1; | |
else if(ele < a[MID] && ele > a[P1]) | |
{ | |
FIRST = P1 + 1; | |
LAST = MID - 1; | |
} | |
else if(ele > a[MID] && ele > a[P2]) | |
FIRST = P2 + 1; | |
else if(ele > a[MID] && ele < a[P2]) | |
{ | |
FIRST = MID + 1; | |
LAST = P2 - 1; | |
} | |
} | |
return loc; | |
} | |
void QuadraticSearch::display() | |
{ | |
if (loc == -1) | |
std::cout<<"Element "<<ele<<" not found in the array"<<std::endl; | |
else | |
std::cout<<"Element is found at the location = "<<loc + 1<<std::endl; | |
} | |
int main() | |
{ | |
QuadraticSearch Qs; | |
Qs.inputData(); | |
Qs.search(); | |
Qs.display(); | |
getchar(); | |
return 0; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment