mercredi 12 août 2020

Need your opinion about a custom made binary search in C++ [closed]

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