I am currently reading a C++ book. I came across the topic were "Binary Search" was mentioned but I didn't read any code examples as I wanted to test my self. So I read the definition of "Binary Search" and tried to implement it with code. Here is what I came up with :
//startv represents the beginning of the range of the elements we are searching in
//endv represents the end of the range of the elements we are searching in
//cnt represents the difference between the position of k now and the position of k one iteration before (if sought is in the first half)
//cnt2 represets the difference between the position of k one iteration before and the position of k now (if sought is in the second half)
const vector<int> vecint = {12, 15, 26, 29, 33, 40, 51, 57, 64, 78, 82, 88, 90, 95, 99, 123, 145, 146, 147, 148, 149, 150};
decltype(vecint.size()) tmp, tmp2, cnt, cnt2, startv, endv, k = (vecint.size() - 1) / 2;
int sought = 0, h1 = 0, h2 = 0;
cout << "Enter the number that you are seeking below:" << endl; //Must type a number present in the vector vecint
cin >> sought;
for (decltype(vecint.size()) i = 0; i <= vecint.size() - 1; i++)
{
if (vecint[k] == sought)
{
cout << sought << " is at position " << k << endl;
break;
}
else if (vecint[k] > sought)
{
if (h2) //sought is present in the second half of the vector vecint
{
startv = k - cnt2;
endv = k;
k = (startv + endv) / 2;
}
else //sought is present in the first half of the vector vecint
{
startv = 0;
endv = k;
tmp = k;
k = (startv + endv) / 2;
cnt = tmp - k;
h1++;
}
}
else if (vecint[k] < sought)
{
if (h1) //sought is present in the first half of the vector vecint
{
startv = k;
endv = k + cnt;
k = (startv + endv) / 2;
}
else //sought is present in the second half of the vector vecint
{
h2++;
startv = k;
endv = vecint.size() - 1;
tmp2 = k;
k = (startv + endv) / 2;
cnt2 = k - tmp2;
if ((vecint.size() - 1) - k == 1) //if k = (startv + endv) / 2; yields the same value as k
{
k++;
}
}
}
}
I am still a beginner and I'd love to increase my knowledge and yours too. So I just wanted to know your opinion about the code, and if there is a major or minor flaw that I'v missed. And of course your thoughts about any way to improve it and make it more efficient.
Thanks very much in advance!
Aucun commentaire:
Enregistrer un commentaire